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:

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.

Grading Criteria: 100 points available for this lab. Bonus points will be issued for those who have a sort that has better compare statistics than the sorts that the instructor implements.
  • The instructor will be using this grading criteria to grade your program/functions. The points will then be scaled to the available points.
  • Here is a C++ style guide from Dr. Fernandez that should assist you in coding your program. Style guide.
  • 100 points if all of the above requirements are met