Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Mergesort and QuicksortReference: Chapters 7-8, Algorithms in Java, 3rd Edition, Robert Sedgewick.2Mergesort and QuicksortTwo great sorting algorithms.! Full scientific understanding of their properties has enabled us to! hammer them into practical system sorts.! Occupies a prominent place in world's computational infrastructure.! Quicksort honored as one of top 10 algorithms for science andengineering of 20th century.Mergesort.! Java sort for objects.! Perl stable, Python stable.Quicksort.! Java sort for primitive types.! C qsort, Unix, g++, Visual C++, Perl, Python.Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Mergesort4MergesortMergesort.! Divide array into two halves.! Recursively sort each half.! Merge two halves to make sorted whole.Jon von Neumann (1945)5Mergesort: Example6MergingMerging. Combine two pre-sorted lists into a sorted whole.How to merge efficiently? Use an auxiliary array.A G L O R H I M S TA G H I L Mfor (int k = l; k < r; k++) aux[k] = a[k];int i = l, j = m;for (int k = l; k < r; k++) { if (i >= m) a[k] = aux[j++]; else if (j >= r) a[k] = aux[i++]; else if (less(aux[j], aux[i])) a[k] = aux[j++]; else a[k] = aux[i++];}ijkl rmauxa7Mergesort: Java Implementationpublic class Merge { private static void sort(Comparable[] a, Comparable[] aux, int l, int r) { if (r <= l + 1) return; int m = (r + l) / 2; sort(a, aux, l, m); sort(a, aux, m, r); merge(a, aux, l, m, r); } public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length); }}lm r10 11 12 13 14 15 16 17 18 198Mergesort Analysis: MemoryQ. How much memory does mergesort require?! Original input array = N.! Auxiliary array for merging = N.! Local variables: constant.! Function call stack: log2 N.! Total = 2N + O(log N).Q. How much memory do other sorting algorithms require?! N + O(1) for insertion sort and selection sort.! In-place = N + O(log N).Challenge for the bored. In-place merge. [Kronrud, 1969]9Mergesort Analysis: Running TimeDef. T(N) = number of comparisons to mergesort an input of size N.Mergesort recurrence.Solution. T(N) = O(N log2 N).! Note: same number of comparisons for any input of size N.! We prove T(N) = N log2 N when N is a power of 2, and = instead of !. ! T (N ) " 0 if N =1T N /2# $( )solve left half1 2 4 3 4 4 + T N /2% &( )solve right half1 2 4 3 4 4 + Nmerging{otherwise' ( ) * ) including already sorted10Proof by Recursion TreeT(N)T(N/2)T(N/2)T(N/4)T(N/4)T(N/4) T(N/4)T(2) T(2)T(2) T(2) T(2) T(2) T(2) T(2)NT(N / 2k)2(N/2)4(N/4)2k (N / 2k)N/2 (2). . .. . .log2NN log2N ! T (N ) =0 if N = 12T (N /2)sorting both halves1 2 4 3 4 + Nmerging{otherwise" # $ % $ 11Proof by InductionClaim. If T(N) satisfies this recurrence, then T(N) = N log2 N.Pf. (by induction on n)! Base case: n = 1.! Inductive hypothesis: T(n) = n log2 n.! Goal: show that T(2n) = 2n log2 (2n). ! T(2n) = 2T (n) + 2n= 2n log2n + 2n= 2n log2(2n) "1( ) + 2n= 2n log2(2n)assumes N is a power of 2 ! T (N ) =0 if N = 12T (N /2)sorting both halves1 2 4 3 4 + Nmerging{otherwise" # $ % $ 12Mergesort: Practical ImprovementsUse sentinel. Two statements in inner loop are array-bounds checking.Use insertion sort on small subarrays.! Mergesort has too much overhead for tiny subarrays.! Cutoff to insertion sort for " 7 elements.Stop if already sorted.! Is biggest element in first half ! smallest element in second half?! Helps for nearly ordered lists.Eliminate the copy to the auxiliary array. Save time (but not space)by switching the role of the input and auxiliary array in eachrecursive call.13Sorting Analysis SummaryRunning time estimates:! Home pc executes 108 comparisons/second.! Supercomputer executes 1012 comparisons/second.Lesson 1. Good algorithms are better than supercomputers.computerhomesuperthousandinstantinstantmillion2.8 hours1 secondbillion317 years1.6 weeksInsertion Sort (N2)thousandinstantinstantmillion1 secinstantbillion18 mininstantMergesort (N log N)Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226QuicksortSir Charles Antony Richard Hoare1980 Turing Award15QuicksortQuicksort.! Shuffle the array.! Partition array so that:– element a[i] is in its final place for some i– no larger element to the left of i– no smaller element to the right of i! Sort each piece recursively.Q. How do we partition in-place efficiently?16Quicksort Partitioning17Quicksort Example18Quicksort: Java Implementationpublic class Quick { public static void sort(Comparable[] a) { Random.shuffle(a); sort(a, 0, a.length - 1); } private static void sort(Comparable[] a, int l, int r) { if (r <= l) return; int m = partition(a, l, r); sort(a, l, m-1); sort(a, m+1, r); }19Quicksort: Java Implementationprivate static int partition(Comparable[] a, int l, int r) { int i = l - 1; int j = r; while(true) { while (less(a[++i], a[r])) if (i == r) break; while (less(a[r], a[--j])) if (j == l) break; if (i >= j) break; exch(a, i, j); } exch(a, i, r); return i;} swap with partitioning elementcheck if pointers crossfind item on right to swapfind item on left to swapswapreturn index where crossing occurs20Quicksort Implementation DetailsPartitioning in-place. Using a spare array makes partitioning easier, butis not worth the cost.Terminating the loop. Testing whether the pointers cross is a bittrickier than it might seem.Staying in bounds. The (i == r) test is redundant, but the (j == l)test is not.Preserving randomness. Shuffling is key for performance guarantee.Equal keys. When duplicates are present, it is (counter-intuitively)best to stop on elements equal to partitioning element.21Quicksort: Performance CharacteristicsWorst case. Number of comparisons is quadratic.! N + (N-1) + (N-2) + . . . + 1 = N(N+1)/2! More likely that your computer is struck by lightning.Caveat. Many textbook implementations go quadratic if input:! Is sorted.! Is reverse sorted.! Has many duplicates.22Quicksort: Average CaseAverage case running time.! Roughly 2 N ln N comparisons.! Assumption: file is randomly shuffled.Remarks.! 39% more comparisons than mergesort.! Faster than mergesort in practice because of lower cost of otherhigh-frequency instructions.! Caveat: many textbook implementations have best case N2 ifduplicates,
View Full Document
Unlocking...