Programming Project 5

Due : Wed., April 1             CSCI 271                               Spring 2009

Problem:

Compare an O(n²) sort with an O(n log n) sort.  To do this, you will program the insertion sort and the quicksort.  You will not need to use classes in this project.

Our project input:

The input will be character strings of length less than or equal to 30 characters.  They will come from the file /home/win.thackerw/271/sort.dat.

Our project output:

Your program will print out the CPU time.  You get the time by using the time function in Unix.  If your program is called p4 then instead of issuing the command p4 to run your program, you use time p4.  This will run your program and report system (sys), user, and real times.  The time of interest for us is user+sys.  You (not your program) should produce a table of the form:

Additionally, you must graph the results.  Also, do the Quicksort on data of size 1,000,000.  Some of these arrays may be too big for static declaration.  Instead you can use the new command to create an array of appropriate size.  This gets the data from the heap and not from static area (which is more limited).

Project Options

For extra credit, you may do an additional O(n²) sort (ex. insertion, selection) AND an additional O(n log n) sort (ex., merge sort, heap sort). For other extra credit, find the point where switching from quicksort to insertion sort (as described in class) is beneficial and implement that quicksort.  Include those times in the table and a description of how you determined the crossover point.