COSC 1436 Lab 9
Purpose: This lab focuses on sorting.
Due: Before class, Section 2, April 2, 2013 and for Section 3, April 4,2013
Requirements:
1. Choose three sort algorithms that you will implement, you must have at least one O(n^2) sort and one O(n * lg n) sort in the algorithms you select. You may use your text, the Internet, and other sources (except each other), to find the code/pseudocode for each sort. You will need to instrument your sorts as described below. The sorts must work properly when the data contains duplicate values. Remember to properly attribute each sort to the author or location where you found it. Test your sorts and verify they work properly with integer data.
2. You will be generating random integer data to test your sorts with a range of 0 to 32,767. Use will be using the rand function as described in your text pages 133  134. Start off generating 32 random numbers in an array and sending them to each sort algorithm (remember to save an unsorted copy of the array to use for the other sort algorithms). Then double the number of random numbers to 64 numbers. Keep doubling until a sort takes over 70 seconds on your test system (complete that sort and then pull that sort from the sorts to be tested in the next iteration). Keep doing this until the fastest sort takes over 70 seconds.
3. All of your sorts are to be instrumented to record the number of compares and the time each sort takes. The final output from your program should be a table that looks approximately like the following (the array size should go much larger), with your data included:
Array Size

Bubble Compares

Bubble Time

Quick Sort Compares

Quick Sort Time

Radix Compares

Radix Time

32


64


128


256


512


1024


2048


4096


8192


16384


32768


65536


131072


262144

Make sure that you only time the actual time each sort takes, not including the time needed to generate the random numbers or copy the numbers between arrays.
4. All output should be to the console. You need to design your output formats, but it should be very clear what has happened. Here is what my sample output looked like using 7 sorts: lab07lny.txt
 Your Name
Purpose of this program. Program psuedocode/flowchart
 Program source code
 Program output
 Include in your documentation your version of the table shown above showing the data from yoour sorts and an analysis of how well each sort met or did not meet its theoretical Big O value. For any where the sort did not meet the theoretical Big O value, provide an analysis why you think it did not meet the theoretical value.
 How was this program tested
 What problems/successes did you have with this program?
 An estimate of how much time you spent working on this lab
6. You will be submitting this lab via Blackboard. You will need to zip your files together and then upload your zipped submission to Blackboard. Make sure you include the source code and the rest of the documentation package, but not the executable files. The source code for your programs, called lab09***.cpp. Put your initials where the 3 asterisks appear. This files must be ready to compile using the standard g++ compiler.