Lab 3: Quicksort


Implement quicksort, plot the results using gnuplot as in Lab 2.


  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]));
  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
      // 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(n2).
  8. Use gnuplot to plot the resultant graph. Here is a gnuplot script (call it plot.plt) that plots something reasonable:
    # 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!" \
    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

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