Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 22, 2010 4:05:04 PM2.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, Python stable sort.Quicksort.•Java sort for primitive types. •C qsort, Unix, g++, Visual C++, Python.last lecturethis lecture‣quicksort‣selection‣duplicate keys‣system sorts34QuicksortBasic plan.•Shuffle the array.•Partition so that, for some j -element a[j] is in place-no larger element to the left of j-no smaller element 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 elementinputshufflepartitionsort leftsort rightresultQuicksort overviewQuicksort partitioningBasic plan.•Scan i from left for an item that belongs on the right.•Scan j from right for item item that belongs on the left.•Exchange a[i] and a[j].•Continue until pointers cross.5 a[i] i j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15-1 15 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 0 5 E C A I E K L P U T M Q R X O S 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 exchangeresultv6Quicksort: 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 overview7Quicksort: 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 guaranteeQuicksort trace8 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 animation9http://www.sorting-algorithms.com/quick-sort50 random elementsin ordercurrent subarrayalgorithm positionnot in order10Quicksort: implementation detailsPartitioning in-place. Using a spare 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) bestto stop on elements equal to the partitioning element.11Quicksort: 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.3 sec6 minsuperinstant1 second1 weekinstantinstantinstantinstantinstantinstant12Quicksort: best case analysisBest case. Number of compares is ~ N lg N.Worst case. Number of compares is ~ N2 / 2.13Quicksort: worst case analysisProposition I. The average number of compares CN to quicksort an array of N elements is ~ 2N ln N (and the number of exchanges
View Full Document
Unlocking...