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

5. Prepare a lab report/documentation package. All of these items do not need to be in the same file or word document, but the main lab report file must reference each item by name. The lab report must includes the following information:
• 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.