Lab 10: CPS 100E: Sorting Assignment

Change into your cps100e directory and create a lab10 subdirectory. Then change into this directory and copy files by typing what's below (don't forget the trailing dot). 

      cp ~ola/cps100e/lab10/* .

Introduction

This lab assignment is mostly an empirical study of different sorting algorithms whose implementations are given to you. Most of the assignment involves analyzing the algorithms on different kinds of input and making conclusions supported by the evidence you glean from your studies.

The file sortall.cc should be used as a framework around which different sorts will be implemented. You should first compile and run sortall.cc then make the modifications outlined below. It currently runs selectionsort on one vector of 500 ints and one vector of 500 strings, writing output to the screen, and also to two files, selectint.data and selectstr.data.

About sortall.cc

The program sortall.cc uses templated functions to sort. Any class/type that supports the standard comparison operations: 

 <=, >=, ==, !=, >, <
and both input and output operations using streams can be sorted (I/O isn't necessary to sort). A listing of sortall.cc is provided at the end of this writeup.

There are three parts to this assignment

  1. Analyzing and graphing O(n^2) sorts.
  2. Analyzing O(n log n) sorts.
  3. Re-implementing the partition code for quicksort.

Analyzing O(n^2) Sorts

There are three O(n^2) sorts implemented: selection, insertion, and bubble.

You are to run the program and time how long it takes to use selection sort, insertion sort, and bubble sort for arrays of size 400 to 2400 in increments of 400. You will need to make modifications in the main function of sortall.cc. This has already been done for you for selection sort on one vector of ints and one vector of strings. You will then graph this data using the gnuplot graphing program which will generate plots like the one below.

In order to use gnuplot you must set up data files as pairs of x,y coordinates. If selection sort of 400 elements takes 0.523 seconds and of 800 elements takes 0.9873 seconds then a data file called select.data should be created whose first two lines are: 

       400    0.523
       800   0.9873
Note that these data files will be created automatically for you. When you first ran the program before making any changes, it was created for selectint.data and selectstr.data.

For this part of the assignment you will create many (six) data files, two for selection sort, two for insertion sort, and two for bubble sort;, for each sort you'll sort two different kinds of element. Each file will contain 6 lines of data with each line consisting of a number of array elements (400 --- 2400) and the time to sort the array of that many elements as described above. Name these files selectint.data, selectstr.data, and so on depending on whether you're sorting ints or strings. All of this part of the assignment should be done in one run.

Using gnuplot

To use gnuplot just type gnuplot at the UNIX prompt. Now you should see the gnuplot prompt: 

gnuplot>
rather than your normal prompt. You should then type the following line which will graph the three sets of data named by the files in quotes: 
plot "insertint.data" with linespoints 1 1, \
"selectint.data" with linespoints 3 3, ``bubbleint.data'' with linespoints 5 5
(the number-pairs 1 1 and 3 3 indicate the style of line and point to use). You can add another file by using a comma after the ``5 5'', specifying bubblestr.data, and specifying ``linespoints 2 2'' for example. Note that the backslash \ can be used to continue typing a long line on multiple lines (but gnuplot treats this as one line).

This command should generate a plot on the screen. Then you should type 

 gnuplot> set ylabel "time (seconds)"
 gnuplot> set xlabel "# elements sorted"
 gnuplot> replot
which should re-generate the plot with the x-axis and y-axis labeled.

Finally you will create a version of the plot to print by typing 

gnuplot> set terminal postscript
gnuplot> set output "squareplot.ps"
gnuplot> replot

You can then print the plot by typing lpr squareplot.ps (you may have to specify the printer to use, e.g., lpr -Pteerlp1 squareplot.ps). Note that to quit gnuplot you simply type ``quit''.

Put your observations on the these sorts in your README file.

Faster Sorts

There are several faster sorts. Most of them are discussed in Weiss and we will go over some of them in class. For this part of the assignment, make a copy of sortall.cc into sortall2.cc.

In doing this part of the assignment you must analyze two sorts as described below.

  1. quick sort
  2. merge sort
You must also re-implement the partition Pivot function.

Timing the faster sorts

First analyze the faster sorts by modifying the program sortall2 so that it sorts arrays of size 10000, 20000, ... 50,000 using these faster sorts (but NOT using O(n^2) sorts which will take too long. REMOVE the O(n^2) sorts). You can plot the data and then include the data as part of your README file showing how long each sort takes for ints and strings. Record your observation in your README file.

Pivot Function

You should change the function Pivot used by quicksort so that rather than split the array into two sections: one less than or equal to the pivot and one greater; the array is split into three sections: one less than the pivot, one equal to the pivot, and one greater than the pivot. The section equal to the pivot does NOT need to be recursively sorted. To do this you may need to change the parameters of the function Pivot. Re-run for JUST quicksort using your changed pivot function; be sure to account for these results in your README file.

(Hint: You'll need an index at the end of the less-than-pivot section, and an index at the end of the equal-to-pivot section. Think about what happens when your program encounters several less-than-pivot elements first followed by an equal-to-pivot element, or vice-versa. Use the PrintArray function on a randomly generated vector of size 100 to make sure that your vector is sorted. Note that when quicksort is applied to small vectors, of size 20 or less, it calls insertionsort, so it is NOT testing your pivot code.)

Submission

You should submit your modified programs and a README file containing the analysis of the routines as described above. Submit these using (where N is your section number, N=1, 2, or 3): 

      submit100e lab10secN sortall.cc sortall2.cc README