# Lab 3: Quicksort

## Objectives

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

## 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(n2).
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