CSC 148H - Assignment #4 - Quicksort

The goal of this assignment is to help you get really familiar with the quicksort sorting method.

Begin by downloading quicksort.py and its associated partition.py. This version of quicksort is different from the one presented in lecture, though the partition procedure is still the same. With this new version of quicksort, please complete the following exercises.

1. The quicksort from lecture used the rightmost element of each sublist as the pivot element. Briefly explain what the quicksort in this assignment uses as its pivot. (15%) Answer in file a4.txt.
2. The quicksort from lecture degrades to O(n^2) running time when the input list is already sorted. This is because the partition procedure first partitions a list of size n, then n-1, then n-2, and so on, for a total of n+n-1+n-2+...+1 = n(n+1)/2 steps. What is the running time of the quicksort given in this assignment on an already-sorted list? Please justify your answer. (20%) Answer in file a4.txt.

Here is another partition procedure that can be used to build a quicksort. The partition procedure from lecture works by maintaining the invariant that the elements less than the pivot come before the split point and the elements at least as big as the pivot come after. This new partition procedure maintains two split points, dividing the list into those elements that are smaller than the pivot, those exactly equal to the pivot, and those strictly larger than the pivot. Use this partition procedure to complete the following exercises.

1. Give an invariant and variant for this new partition procedure. Upon loop termination, your invariant should allow us to conclude that the procedure really works as described here. Be sure that your invariant is true prior to loop execution; that the invariant is maintained by the loop; that your variant is always positive; and that your variant is always decreased. Give some informal justification showing that the loop maintains your invariant and that the loop decreases your variant. (35%) Answer in file a4.txt.
2. Describe how this partition procedure compares to the partition procedure from lecture. In what particular circumstance will using this partition procedure yield a faster quicksort than using the partition procedure from lecture? When will it yield a slower quicksort? You may wish to add code to count the number of "steps" performed by each partition procedure to help you answer this question; you may give us this supporting data, but do not submit any code for this question. (15%) Answer in file a4.txt.
3. Modify quicksort.py (the same one you worked on above) to use this new partition procedure instead of the one from lecture. Your quicksort should be as simple as possible; in particular, you should not perform unnecessary swaps or comparisons. You should also include some justification that your quicksort procedure is correct. (25%). Answer in file quicksort.py with justification in a4.txt.

You should submit only your a4.txt and quicksort.py files, as indicated above.

Note that it is possible to receive up to 110% on this assignment. Marks over 100% will act as bonus marks.