QuicksortA short list of categoriesQuicksort IPartitioning (Quicksort II)Partitioning IIPartitioningExample of partitioningThe partition method (Java)The quicksort method (in Java)Analysis of quicksort—best casePartitioning at various levelsBest case IIWorst caseWorst case partitioningWorst case for quicksortTypical case for quicksortTweaking QuicksortPicking a better pivotMedian of threeFinal commentsThe EndQuicksort2A short list of categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithms3Quicksort ITo sort a[left...right]:1. if left < right:1.1. Partition a[left...right] such that: all a[left...p-1] are less than a[p], and all a[p+1...right] are >= a[p]1.2. Quicksort a[left...p-1]1.3. Quicksort a[p+1...right]2. Terminate4Partitioning (Quicksort II)A key step in the Quicksort algorithm is partitioning the arrayWe choose some (any) number p in the array to use as a pivotWe partition the array into three parts:pnumbers less than pnumbers greater than or equal to p p5Partitioning IIChoose an array value (say, the first) to use as the pivotStarting from the left end, find the first element that is greater than or equal to the pivotSearching backward from the right end, find the first element that is less than the pivotInterchange (swap) these two elementsRepeat, searching from where we left off, until done6PartitioningTo partition a[left...right]:1. Set pivot = a[left], l = left + 1, r = right;2. while l < r, do2.1. while l < right & a[l] < pivot , set l = l + 12.2. while r > left & a[r] >= pivot , set r = r - 12.3. if l < r, swap a[l] and a[r]3. Set a[left] = a[r], a[r] = pivot 4. Terminate7Example of partitioningchoose pivot: 4 3 6 9 2 4 3 1 2 1 8 9 3 5 6search: 4 3 6 9 2 4 3 1 2 1 8 9 3 5 6swap: 4 3 3 9 2 4 3 1 2 1 8 9 6 5 6search: 4 3 3 9 2 4 3 1 2 1 8 9 6 5 6swap: 4 3 3 1 2 4 3 1 2 9 8 9 6 5 6search: 4 3 3 1 2 4 3 1 2 9 8 9 6 5 6swap: 4 3 3 1 2 2 3 1 4 9 8 9 6 5 6search: 4 3 3 1 2 2 3 1 4 9 8 9 6 5 6 (left > right)swap with pivot: 1 3 3 1 2 2 3 4 4 9 8 9 6 5 68The partition method (Java) static int partition(int[] a, int left, int right) { int p = a[left], l = left + 1, r = right; while (l < r) { while (l < right && a[l] < p) l++; while (r > left && a[r] >= p) r--; if (l < r) { int temp = a[l]; a[l] = a[r]; a[r] = temp; } } a[left] = a[r]; a[r] = p; return r; }9The quicksort method (in Java) static void quicksort(int[] array, int left, int right) { if (left < right) { int p = partition(array, left, right); quicksort(array, left, p - 1); quicksort(array, p + 1, right); }}10Analysis of quicksort—best caseSuppose each partition operation divides the array almost exactly in halfThen the depth of the recursion in log2nBecause that’s how many times we can halve nHowever, there are many recursions!How can we figure this out?We note thatEach partition is linear over its subarrayAll the partitions at one level cover the array11Partitioning at various levels12Best case II We cut the array size in half each timeSo the depth of the recursion in log2n At each level of the recursion, all the partitions at that level do work that is linear in nO(log2n) * O(n) = O(n log2n) Hence in the average case, quicksort has time complexity O(n log2n)What about the worst case?13Worst caseIn the worst case, partitioning always divides the size n array into these three parts:A length one part, containing the pivot itselfA length zero part, andA length n-1 part, containing everything elseWe don’t recur on the zero-length partRecurring on the length n-1 part requires (in the worst case) recurring to depth n-114Worst case partitioning15Worst case for quicksortIn the worst case, recursion may be n levels deep (for an array of size n)But the partitioning work done at each level is still nO(n) * O(n) = O(n2)So worst case for Quicksort is O(n2)When does this happen?There are many arrangements that could make this happenHere are two common cases:When the array is already sortedWhen the array is inversely sorted (sorted in the opposite order)16Typical case for quicksortIf the array is sorted to begin with, Quicksort is terrible: O(n2)It is possible to construct other bad casesHowever, Quicksort is usually O(n log2n)The constants are so good that Quicksort is generally the fastest algorithm knownMost real-world sorting is done by Quicksort17Tweaking QuicksortAlmost anything you can try to “improve” Quicksort will actually slow it downOne good tweak is to switch to a different sorting method when the subarrays get small (say, 10 or 12)Quicksort has too much overhead for small array sizesFor large arrays, it might be a good idea to check beforehand if the array is already sortedBut there is a better tweak than this18Picking a better pivotBefore, we picked the first element of the subarray to use as a pivotIf the array is already sorted, this results in O(n2) behaviorIt’s no better if we pick the last elementWe could do an optimal quicksort (guaranteed O(n log n)) if we always picked a pivot value that exactly cuts the array in halfSuch a value is called a median: half of the values in the array are larger, half are smallerThe easiest way to find the median is to sort the array and pick the value in the middle (!)19Median of threeObviously, it doesn’t make sense to sort the array in order to find the median to use as a pivotInstead, compare just three elements of our (sub)array—the first, the last, and the middleTake the median (middle value) of these three as pivotIt’s possible (but not easy) to construct cases which will make this technique O(n2)Suppose we rearrange (sort) these three numbers so that the smallest is in the first position, the largest in the last position, and the other in the middleThis lets us simplify and speed up the partition loop20Final commentsQuicksort is the fastest known sorting algorithmFor optimum efficiency, the pivot must be chosen carefully“Median of three” is a good technique for choosing the pivotHowever, no matter what you do, there will be some cases where Quicksort runs in
View Full Document