Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·February 22, 2012 5:24:30 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E2.3 QUICKSORT‣quicksort‣selection‣duplicate keys‣system sorts2Two classic sorting algorithmsCritical components in the world’s computational infrastructure.•Full scientific understanding of their properties has enabled usto develop them into practical system sorts.•Quicksort honored as one of top 10 algorithms of 20th centuryin science and engineering.Mergesort.•Java sort for objects.•Perl, C++ stable sort, Python stable sort, Firefox JavaScript, ...Quicksort.•Java sort for primitive types. •C qsort, Unix, Visual C++, Python, Matlab, Chrome JavaScript, ...last lecturethis lecture3Quicksort t-shirt‣quicksort‣selection‣duplicate keys‣system sorts45QuicksortBasic plan.•Shuffle the array.•Partition so that, for some j -entry a[j] is in place-no larger entry to the left of j-no smaller entry to the right of j•Sort each piece recursively.Sir Charles Antony Richard Hoare1980 Turing AwardQ U I C K S O R T E X A M P L EK R A T E L E P U I M Q C X O SE C A I E K L P U T M Q R X O SA C E E I K L P U T M Q R X O SA C E E I K L M O P Q R S T U XA C E E I K L M O P Q R S T U Xnot greater not lesspartitioning iteminputshufflepartitionsort leftsort rightresultQuicksort overviewQuicksort partitioning demo6Quicksort partitioningBasic plan.•Scan i from left for an item that belongs on the right.•Scan j from right for an item that belongs on the left.•Exchange a[i] and a[j].•Repeat until pointers cross.7 a[i] i j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 16 K R A T E L E P U I M Q C X O S 1 12 K R A T E L E P U I M Q C X O S 1 12 K C A T E L E P U I M Q R X O S 3 9 K C A T E L E P U I M Q R X O S 3 9 K C A I E L E P U T M Q R X O S 5 6 K C A I E L E P U T M Q R X O S 5 6 K C A I E E L P U T M Q R X O S 6 5 K C A I E E L P U T M Q R X O S 6 5 E C A I E K L P U T M Q R X O S 6 5 E C A I E K L P U T M Q R X O SPartitioning trace (array contents before and after each exchange)initial valuesscan left, scan rightexchangescan left, scan rightexchangescan left, scan rightexchangescan left, scan rightfinal exchangeresultv8Quicksort: Java code for partitioningprivate static int partition(Comparable[] a, int lo, int hi){ int i = lo, j = hi+1; while (true) { while (less(a[++i], a[lo])) if (i == hi) break; while (less(a[lo], a[--j])) if (j == lo) break; if (i >= j) break; exch(a, i, j); } exch(a, lo, j); return j;} swap with partitioning itemcheck if pointers crossfind item on right to swapfind item on left to swapswapreturn index of item now known to be in placei! v" vjvvlo hilo hiv! v" vjbeforeduringafterQuicksort partitioning overviewi! v" vjvvlo hilo hiv! v" vjbeforeduringafterQuicksort partitioning overviewi! v" vjvvlo hilo hiv! v" vjbeforeduringafterQuicksort partitioning overview9Quicksort: Java implementationpublic class Quick{ private static int partition(Comparable[] a, int lo, int hi) { /* see previous slide */ } public static void sort(Comparable[] a) { StdRandom.shuffle(a); sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); }} shuffle needed for performance guarantee(stay tuned)Quicksort trace10 lo j hi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Q U I C K S O R T E X A M P L E K R A T E L E P U I M Q C X O S 0 5 15 E C A I E K L P U T M Q R X O S 0 3 4 E C A E I K L P U T M Q R X O S 0 2 2 A C E E I K L P U T M Q R X O S 0 0 1 A C E E I K L P U T M Q R X O S 1 1 A C E E I K L P U T M Q R X O S 4 4 A C E E I K L P U T M Q R X O S 6 6 15 A C E E I K L P U T M Q R X O S 7 9 15 A C E E I K L M O P T Q R X U S 7 7 8 A C E E I K L M O P T Q R X U S 8 8 A C E E I K L M O P T Q R X U S 10 13 15 A C E E I K L M O P S Q R T U X 10 12 12 A C E E I K L M O P R Q S T U X 10 11 11 A C E E I K L M O P Q R S T U X 10 10 A C E E I K L M O P Q R S T U X 14 14 15 A C E E I K L M O P Q R S T U X 15 15 A C E E I K L M O P Q R S T U X A C E E I K L M O P Q R S T U X no partition for subarrays of size 1initial valuesrandom shuffleresultQuicksort trace (array contents after each partition)Quicksort animation11http://www.sorting-algorithms.com/quick-sort50 random itemsin ordercurrent subarrayalgorithm positionnot in order12Quicksort: implementation detailsPartitioning in-place. Using an extra array makes partitioning easier(and stable), but is not worth the cost.Terminating the loop. Testing whether the pointers cross is a bit trickierthan it might seem.Staying in bounds. The (j == lo) test is redundant (why?),but the (i == hi) test is not.Preserving randomness. Shuffling is needed for performance guarantee.Equal keys. When duplicates are present, it is (counter-intuitively) betterto stop on keys equal to the partitioning item's key.13Quicksort: empirical analysisRunning time estimates:•Home PC executes 108 compares/second.•Supercomputer executes 1012 compares/second.Lesson 1. Good algorithms are better than supercomputers.Lesson 2. Great algorithms are better than good ones.insertion sort (Ninsertion sort (Ninsertion sort (N2)mergesort (N log N)mergesort (N log N)mergesort (N log N)quicksort (N log N)quicksort (N log N)quicksort (N log N)computerthousandmillionbillionthousandmillionbillionthousandmillionbillionhomeinstant2.8 hours317 yearsinstant1 second18 mininstant0.6 sec12 minsuperinstant1 second1 weekinstantinstantinstantinstantinstantinstant14Quicksort: best-case analysisBest case. Number of compares is ~ N lg N.random
View Full Document
Unlocking...