CS 240: Lecture 21 – Quicksort
Dear students:
Mergesort has some nice worst case running time, but have you check out quicksort? It too takes a recursive, divide-and-conquer approach to sorting. Here’s the overall algorithm:
public static void quicksort(int[] items) {
quicksort(items, 0, items.length - 1);
}
private static void quicksort(int[] items,
int left,
int right) {
int pivotIndex = (left + right) / 2;
pivotIndex = partition(items, left, right, pivotIndex);
// Sort left.
if (pivotIndex - left > 1) {
quicksort(items, left, pivotIndex - 1);
}
// Sort right.
if (right - pivotIndex > 1) {
quicksort(items, pivotIndex + 1, right);
}
}
What’s different about quicksort compared to mergesort? Mergesort required scratch space that was at least as big as the original array. We’ve been focusing on time complexity, but space complexity can also be a concern. Quicksort doesn’t require that extra space.
An in-place sorting algorithm doesn’t need an extra chunk of memory to do its work. By this definition, mergesort is not an in-place sorting algorithm. Is quicksort? Is selection sort? Is insertion sort?
The recursive pattern is also a bit different. With mergesort, the structure is sort-left, sort-right, and merge. With quicksort, the structure is partition, sort-left, and sort-right. As with mergesort, the helper method is where the magic of sorting really takes place. We will walk through this partition method:
private static int partition(int[] items,
int left,
int right,
int pivotIndex) {
int pivot = items[pivotIndex];
swap(items, pivotIndex, right); // Stick pivot at end
pivotIndex = right; // remember where it is.
right--;
// Advance from both ends until window collapses.
while (left <= right) {
// Skip rightward past < pivots.
while (items[left] < pivot) {
left++;
}
// Skip leftward past >= pivots.
while ((right >= left) && (items[right] >= pivot)) {
right--;
}
// Swap out-of-place pair.
if (right > left) {
swap(items, left, right);
}
}
// Put pivot between < and >=.
swap(items, left, pivotIndex);
return left;
}
Exercises
The rest of our time together will be devoted to solving exercises in small groups.
When the exercises ask you to count comparisons, restrict your counting to comparisons that involve just the keys. (In our simplified algorithm that sorts integers, the keys are the elements themselves.) Do not count only comparisons that compare indices. Comparing keys is generally more costly than comparing integer indices, so counting them gives us a reasonable measure of our algorithm’s performance.
TODO
You have some work to do before the next class:
- Read sections 11.13-11.14 in OpenDSA.
- Solve at least three of the LeetCode exercises from lab.
See you next time.
P.S. It’s time for a haiku!
How do you picksort?
You kicksort and you licksort
Choose one that clicksort