Lab 3: Quicksort

Objectives

Assignment

1. In this lab we want to redo Lab 2 by including the empirical timing results of quicksort into the runtime plot.
2. As before, use your array_t class to store random integer values, e.g.,

   #include "array.h"
   
   	array_t<int>	A(atoi(argv[1]));
   
     A.randseed();
     A.randfill();
   	

3. You will need to write a public member function quicksort() for the array_t class.
4. Quicksort Algorithm:
   1. Pick any element v. This is called the pivot.
   2. Put all elements less than v on the left of the array. The others go on the right. This is called partitioning.
   3. Recursively quicksort each half of the array.
5. Your main() routine should then include:

   int main()
   {
     // read in desired array size
     // declare array variable A
     ...
     // start the timer
     A.quicksort(0,A.size()-1);
     // stop the timer
     // report the timer value
   }
   	

   Note the passing in of left and right integer indeces into quicksort(). Recall that quicksort is recursive and operates "in place" on the array, working over the items within the [left,right] array bounds.
6. Print the sorted values for a small list to make sure the sort is working. Then measure and report (turn in) the time required to sort 5, 50, 500, 5,000, 50,000, and 500,000 integers.
7. Once again we want two things:
   1. a quicksort.dat data file that contains two columns of numbers: the first column is n, the size of the array, and the second column is t, the time taken to sort the array.
   2. a plot of both bubblesort.dat and quicksort.dat data files showing their run times graphically against various other theoretical bounds, e.g., O(n), O(log n), O(n²).
8. Use gnuplot to plot the resultant graph. Here is a gnuplot script (call it plot.plt) that plots something reasonable:

   reset
   # this should work but need to add fontpath -- could be system-specific
   set fontpath \
     "/sw/share/texmf-dist/fonts/type1!" \
     "/usr/share/texmf/fonts/type1!" \
     "/usr/local/teTeX/share/texmf-dist/fonts/type1!" \
     "/usr/share/texmf-texlive/fonts/type1!"
   set term postscript eps enhanced "NimbusSanL-Regu" 22 \
     fontfile "uhvr8a.pfb" fontfile "usyr.pfb" fontfile "utmri8a.pfb"
   set xrange [*:*]
   set xtics (0,50,500)
   set yrange [-500:5000]
   set key top right
   set title "Runtime vs. Dataset Size"
   set ylabel "Runtime (s)"
   set xlabel "Dataset Size (n/1000)"
   set output 'plot.eps'
   plot \
     x**2 title "O(n^2)" \
       with lines lt 1 lw 3 lc rgb "#ff7f00", \
     'bubblesort.dat' using ($1)/1000:($2)/1000 title "bubblesort" \
       with linespoints pt 4 ps 2 lt 1 lw 3 lc rgb "#377eb8",\
     'quicksort.dat' using ($1)/1000:($2)/1000 title "quicksort" \
       with linespoints pt 4 ps 2 lt 1 lw 3 lc rgb "#e41a1c",\
     x title "O(n)" \
       with lines lt 1 lw 3 lc rgb "#4daf4a",\
     log10(x)/log10(2) title "O(log_2 n)" \
       with lines lt 1 lw 3 lc rgb "#984ea3"
   	

   Run the above script with the command

   gnuplot plot.plt
   	

9. The above gnuplot file will create an encapsulated PostScript file, or .eps file; convert this to something more useful, like a PDF plot, via the command

   epstopdf --nocompress -o=plot.pdf plot.eps
   	

10. In fact, while you're at it, stick both of the above gnuplot and epstopdf commands into a plot: target in your Makefile. Then, rewrite your program to accept the size of array you want as input argument argv[1] and have it write out the time to sort to std::cout. This way, you can script the run (and plot) within the Makefile so that a run target executes the following:

            ./main 5 >> quicksort.dat
            ./main 500 >> quicksort.dat
            ./main 5000 >> quicksort.dat
            ./main 50000 >> quicksort.dat
            ./main 500000 >> quicksort.dat
    	

    then all you'll need to do to "automate" the entire process is type:

    make main
    make run
    make plot
    	

11. The end result of this lab is a plot like you see below. You'll notice that quicksort does much better than bubblesort.
    

Implementation Details

• Partitioning:
  1. Choose a pivot and move it out of the way. (See below)
  2. Create two counter integers (i and j). Start i at left and j at right-1.
  3. As long as array[i] is less than the pivot, increment i.
  4. Now starting with the other end, as long as j is greater than (or equal to) the pivot, decrement j. At this point, element i and j are both holding elements that are out of position.
  5. Make sure that i is still an index to the left of j. If it isn't, we're done with partitioning. If it is, swap elements i and j. (Write a swap function.)
  6. Continue with steps 3-6 as long as i is less than j.
  7. After the partitioning is complete, swap the pivot into the center (element i).
  8. Recursively quicksort elements left through i-1.
  9. Recursively quicksort elements i+1 through right.
  10. The pivot is already in the right position. You are finished.
• Picking a pivot:
  1. You can use the first, last, or middle element in the array to be the pivot. However if the array is partially sorted or reverse sorted, the first or last elements are likely to be bad choices. The middle element runs less risk, and can be selected by computing index: left + (right - left)/2
  2. Alternatively, you should use the array's median as the pivot. This can be found in linear O(n) time.
• Sorting in place:
  1. A benefit the quicksort has over the mergesort (in addition to speed) is that it requires no extra memory for sorting, because we sort it in the source array.
  2. This approach means that we must keep track of which section of the array we are sorting.
  3. Do this by passing the recursive function left and right indeces specifying what section to sort.

Turn in

Turn in all of your code, in one tar.gz archive of your lab02/ directory, including:

1. A README file containing
   1. Course id--section no
   2. Name
   3. Lab description
   4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
   5. Lessons learned, identified interesting features of your program
   6. Any special usage instructions
2. Makefile
3. source code (.h headers and .cpp source)
4. object code (do a make clean before tar)

How to hand in

See sendlab notes