DOC PREVIEW
Penn CIT 594 - Quicksort

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 categoriesAlgorithm types we will consider include:Simple recursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithmsBranch and bound algorithmsBrute force algorithmsRandomized algorithms3Quicksort ITo 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 arrayWe choose some (any) number p in the array to use as a pivotWe partition the array into three parts:pnumbers less than pnumbers greater than or equal to p p5Partitioning IIChoose an array value (say, the first) to use as the pivotStarting from the left end, find the first element that is greater than or equal to the pivotSearching backward from the right end, find the first element that is less than the pivotInterchange (swap) these two elementsRepeat, searching from where we left off, until done6PartitioningTo 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 partitioningchoose pivot: 4 3 6 9 2 4 3 1 2 1 8 9 3 5 6search: 4 3 6 9 2 4 3 1 2 1 8 9 3 5 6swap: 4 3 3 9 2 4 3 1 2 1 8 9 6 5 6search: 4 3 3 9 2 4 3 1 2 1 8 9 6 5 6swap: 4 3 3 1 2 4 3 1 2 9 8 9 6 5 6search: 4 3 3 1 2 4 3 1 2 9 8 9 6 5 6swap: 4 3 3 1 2 2 3 1 4 9 8 9 6 5 6search: 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 caseSuppose each partition operation divides the array almost exactly in halfThen the depth of the recursion in log2nBecause that’s how many times we can halve nHowever, there are many recursions!How can we figure this out?We note thatEach partition is linear over its subarrayAll the partitions at one level cover the array11Partitioning at various levels12Best case II We cut the array size in half each timeSo 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 nO(log2n) * O(n) = O(n log2n) Hence in the average case, quicksort has time complexity O(n log2n)What about the worst case?13Worst caseIn the worst case, partitioning always divides the size n array into these three parts:A length one part, containing the pivot itselfA length zero part, andA length n-1 part, containing everything elseWe don’t recur on the zero-length partRecurring on the length n-1 part requires (in the worst case) recurring to depth n-114Worst case partitioning15Worst case for quicksortIn 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 nO(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 happenHere are two common cases:When the array is already sortedWhen the array is inversely sorted (sorted in the opposite order)16Typical case for quicksortIf the array is sorted to begin with, Quicksort is terrible: O(n2)It is possible to construct other bad casesHowever, Quicksort is usually O(n log2n)The constants are so good that Quicksort is generally the fastest algorithm knownMost real-world sorting is done by Quicksort17Tweaking QuicksortAlmost anything you can try to “improve” Quicksort will actually slow it downOne 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 sizesFor large arrays, it might be a good idea to check beforehand if the array is already sortedBut there is a better tweak than this18Picking a better pivotBefore, we picked the first element of the subarray to use as a pivotIf the array is already sorted, this results in O(n2) behaviorIt’s no better if we pick the last elementWe could do an optimal quicksort (guaranteed O(n log n)) if we always picked a pivot value that exactly cuts the array in halfSuch a value is called a median: half of the values in the array are larger, half are smallerThe easiest way to find the median is to sort the array and pick the value in the middle (!)19Median of threeObviously, it doesn’t make sense to sort the array in order to find the median to use as a pivotInstead, compare just three elements of our (sub)array—the first, the last, and the middleTake the median (middle value) of these three as pivotIt’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 middleThis lets us simplify and speed up the partition loop20Final commentsQuicksort is the fastest known sorting algorithmFor optimum efficiency, the pivot must be chosen carefully“Median of three” is a good technique for choosing the pivotHowever, no matter what you do, there will be some cases where Quicksort runs in


View Full Document

Penn CIT 594 - Quicksort

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Quicksort
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quicksort and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quicksort 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?