Question? Leave a message!




Two classic sorting algorithms: mergesort and quicksort

Two classic sorting algorithms: mergesort and quicksort
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 2.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms FOUR TH EDITION comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduTwo classic sorting algorithms: mergesort and quicksort Critical components in the world’s computational infrastructure. Full scientific understanding of their properties has enabled us to develop them into practical system sorts. th Quicksort honored as one of top 10 algorithms of 20 century in science and engineering. Mergesort. this lecture ... Quicksort. next lecture ... 22.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduMergesort Basic plan. Divide array into two halves. Recursively sort each half. Merge two halves. input M E R G E S O R T E X A M P L E sort left half E E G M O R R S T E X A M P L E sort right half E E G M O R R S A E E L M P T X merge results A E E E E G L M M O P R R S T X Mergesort overview 4Abstract inplace merge demo Goal. Given two sorted subarrays alo to amid and amid+1 to ahi, replace with sorted subarray alo to ahi. lo mid mid+1 hi a E E G M R A C E R T sorted sorted 5Abstract inplace merge demo Goal. Given two sorted subarrays alo to amid and amid+1 to ahi, replace with sorted subarray alo to ahi. lo hi a A C E E E G M R R T sorted 6Merging: Java implementation private static void merge(Comparable a, Comparable aux, int lo, int mid, int hi) for (int k = lo; k = hi; k++) copy auxk = ak; int i = lo, j = mid+1; for (int k = lo; k = hi; k++) if (i mid) ak = auxj++; merge else if (j hi) ak = auxi++; else if (less(auxj, auxi)) ak = auxj++; else ak = auxi++; lo i mid j hi aux A G L O R H I M S T k a A G H I L M 7Mergesort: Java implementation public class Merge private static void merge(...) / as before / private static void sort(Comparable a, Comparable aux, int lo, int hi) if (hi = lo) return; int mid = lo + (hi lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid+1, hi); merge(a, aux, lo, mid, hi); public static void sort(Comparable a) Comparable aux = new Comparablea.length; sort(a, aux, 0, a.length 1); lo mid hi 10 11 12 13 14 15 16 17 18 19 8Mergesort: trace a lo hi 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M E R G E S O R T E X A M P L E merge(a, aux, 0, 0, 1) E M R G E S O R T E X A M P L E merge(a, aux, 2, 2, 3) E M G R E S O R T E X A M P L E merge(a, aux, 0, 1, 3) E G M R E S O R T E X A M P L E merge(a, aux, 4, 4, 5) E G M R E S O R T E X A M P L E merge(a, aux, 6, 6, 7) E G M R E S O R T E X A M P L E merge(a, aux, 4, 5, 7) E G M R E O R S T E X A M P L E merge(a, aux, 0, 3, 7) E E G M O R R S T E X A M P L E merge(a, aux, 8, 8, 9) E E G M O R R S E T X A M P L E merge(a, aux, 10, 10, 11) E E G M O R R S E T A X M P L E merge(a, aux, 8, 9, 11) E E G M O R R S A E T X M P L E merge(a, aux, 12, 12, 13) E E G M O R R S A E T X M P L E merge(a, aux, 14, 14, 15) E E G M O R R S A E T X M P E L merge(a, aux, 12, 13, 15) E E G M O R R S A E T X E L M P merge(a, aux, 8, 11, 15) E E G M O R R S A E E L M P T X merge(a, aux, 0, 7, 15) A E E E E G L M M O P R R S T X Trace of merge results for topdown mergesort result after recursive call 9Mergesort: animation 50 random items algorithm position in order current subarray not in order http://www.sortingalgorithms.com/mergesort 10Mergesort: animation 50 reversesorted items algorithm position in order current subarray not in order http://www.sortingalgorithms.com/mergesort 11Mergesort: empirical analysis Running time estimates: 8 Laptop executes 10 compares/second. 12 Supercomputer executes 10 compares/second. 2 2 2 insertion sort (N insertion sort (N insertion sort (N ) ) ) mer mer mergesort (N log N) gesort (N log N) gesort (N log N) computer thousand million billion thousand million billion home instant 2.8 hours 317 years instant 1 second 18 min super instant 1 second 1 week instant instant instant Bottom line. Good algorithms are better than supercomputers. 12Mergesort: number of compares Proposition. Mergesort uses ≤ N lg N compares to sort an array of length N. Pf sketch. The number of compares C (N) to mergesort an array of length N satisfies the recurrence: C (N) ≤ C (⎡N / 2⎤) + C (⎣N / 2⎦) + N for N 1, with C (1) = 0. left half right half merge result holds for all N We solve the recurrence when N is a power of 2: (analysis cleaner in this case) D (N) = 2 D (N / 2) + N, for N 1, with D (1) = 0. 13Divideandconquer recurrence: proof by picture Proposition. If D (N) satisfies D (N) = 2 D (N / 2) + N for N 1, with D (1) = 0, then D (N) = N lg N. Pf 1. assuming N is a power of 2 D (N) N = N D (N / 2) D (N / 2) 2 (N/2) = N 4 (N/4) D(N / 4) D(N / 4) = N D(N / 4) D(N / 4) lg N D(N / 8) D(N / 8) D(N / 8) D(N / 8) D(N / 8) D(N / 8) D(N / 8) D(N / 8) 8 (N/8) = N ⋮ ⋮ T(N) = N lg N 14Divideandconquer recurrence: proof by induction Proposition. If D (N) satisfies D (N) = 2 D (N / 2) + N for N 1, with D (1) = 0, then D (N) = N lg N. Pf 2. assuming N is a power of 2 Base case: N = 1. Inductive hypothesis: D (N) = N lg N. Goal: show that D (2N) = (2N) lg (2N). given D (2N) = 2 D (N) + 2N inductive hypothesis = 2 N lg N + 2N algebra = 2 N (lg (2N) – 1) + 2N QED = 2 N lg (2N) 15Mergesort: number of array accesses Proposition. Mergesort uses ≤ 6 N lg N array accesses to sort an array of length N. Pf sketch. The number of array accesses A (N) satisfies the recurrence: A (N) ≤ A (⎡N / 2⎤) + A (⎣N / 2⎦) + 6 N for N 1, with A (1) = 0. Key point. Any algorithm with the following structure takes N log N time: public static void linearithmic(int N) if (N == 0) return; linearithmic(N/2); solve two problems of half the size linearithmic(N/2); linear(N); do a linear amount of work Notable examples. FFT, hiddenline removal, Kendalltau distance, … 16Mergesort analysis: memory Proposition. Mergesort uses extra space proportional to N. Pf. The array aux needs to be of length N for the last merge. two sorted subarrays A C D G H I M N U V B E F J O P Q R S T A B C D E F G H I J M N O P Q R S T U V merged result Def. A sorting algorithm is inplace if it uses ≤ c log N extra memory. Ex. Insertion sort, selection sort, shellsort. Challenge 1 (not hard). Use aux array of length ½ N instead of N. Challenge 2 (very hard). Inplace merge. Kronrod 1969 17Mergesort: practical improvements Use insertion sort for small subarrays. Mergesort has too much overhead for tiny subarrays. Cutoff to insertion sort for ≈ 10 items. private static void sort(Comparable a, Comparable aux, int lo, int hi) if (hi = lo + CUTOFF 1) Insertion.sort(a, lo, hi); return; int mid = lo + (hi lo) / 2; sort (a, aux, lo, mid); sort (a, aux, mid+1, hi); merge(a, aux, lo, mid, hi); 18 3.2 Mergesort 235 Mergesort with cutoff to insertion sort: visualization fi rst subarray second subarray fi rst merge fi rst half sorted second half sorted result 19 Visual trace of topdown mergesort for with cutoff for small subarraysMergesort: practical improvements Stop if already sorted. Is largest item in first half ≤ smallest item in second half Helps for partiallyordered arrays. A B C D E F G H I J M N O P Q R S T U V A B C D E F G H I J M N O P Q R S T U V private static void sort(Comparable a, Comparable aux, int lo, int hi) if (hi = lo) return; int mid = lo + (hi lo) / 2; sort (a, aux, lo, mid); sort (a, aux, mid+1, hi); if (less(amid+1, amid)) return; merge(a, aux, lo, mid, hi); 20Mergesort: practical improvements Eliminate the copy to the auxiliary array. Save time (but not space) by switching the role of the input and auxiliary array in each recursive call. private static void merge(Comparable a, Comparable aux, int lo, int mid, int hi) int i = lo, j = mid+1; for (int k = lo; k = hi; k++) if (i mid) auxk = aj++; else if (j hi) auxk = ai++; merge from a to aux else if (less(aj, ai)) auxk = aj++; else auxk = ai++; private static void sort(Comparable a, Comparable aux, int lo, int hi) if (hi = lo) return; int mid = lo + (hi lo) / 2; assumes aux is initialize to a once, sort (aux, a, lo, mid); before recursive calls sort (aux, a, mid+1, hi); merge(a, aux, lo, mid, hi); switch roles of aux and a 21Java 6 system sort Basic algorithm for sorting objects = mergesort. Cutoff to insertion sort = 7. Stopifalreadysorted test. Eliminatethecopytotheauxiliaryarray trick. Arrays.sort(a) http://www.java2s.com/OpenSource/Java/6.0JDKModules/j2me/java/util/Arrays.java.html 222.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduBottomup mergesort Basic plan. Pass through array, merging subarrays of size 1. Repeat for subarrays of size 2, 4, 8, .... ai ai ai ai ai 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 M E R G E S O R T E X A M P L E M E R G E S O R T E X A M P L E M E R G E S O R T E X A M P L E M E R G E S O R T E X A M P L E M E R G E S O R T E X A M P L E sz = 1 sz = 1 sz = 1 sz = 1 sz = 1 merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 00000, 0, , 0, , 0, , 0, , 0, 11111) E M ) E M ) E M ) E M ) E M R G E S O R T E X A M P L E R G E S O R T E X A M P L E R G E S O R T E X A M P L E R G E S O R T E X A M P L E R G E S O R T E X A M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 22222, 2, , 2, , 2, , 2, , 2, 33333) ) ) ) ) E M E M E M E M E M G R G R G R G R G R E S O R T E X A M P L E E S O R T E X A M P L E E S O R T E X A M P L E E S O R T E X A M P L E E S O R T E X A M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 44444, 4, , 4, , 4, , 4, , 4, 55555) ) ) ) ) E M G R E M G R E M G R E M G R E M G R E S E S E S E S E S O R T E X A M P L E O R T E X A M P L E O R T E X A M P L E O R T E X A M P L E O R T E X A M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 66666, 6, , 6, , 6, , 6, , 6, 77777) ) ) ) ) E M G R E S E M G R E S E M G R E S E M G R E S E M G R E S O R O R O R O R O R T E X A M P L E T E X A M P L E T E X A M P L E T E X A M P L E T E X A M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 88888, 8, , 8, , 8, , 8, , 8, 99999) ) ) ) ) E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E T E T E T E T E T X A M P L E X A M P L E X A M P L E X A M P L E X A M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 10 10 10 10 10, 10, , 10, , 10, , 10, , 10, 11 11 11 11 11) ) ) ) ) E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E T E T E T E T E T A X A X A X A X A X M P L E M P L E M P L E M P L E M P L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 12 12 12 12 12, 12, , 12, , 12, , 12, , 12, 13 13 13 13 13) ) ) ) ) E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E T A X E T A X E T A X E T A X E T A X M P M P M P M P M P L E L E L E L E L E merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 14 14 14 14 14, 14, , 14, , 14, , 14, , 14, 15 15 15 15 15) ) ) ) ) E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E M G R E S O R E T A X M P E T A X M P E T A X M P E T A X M P E T A X M P E L E L E L E L E L sz = 2 sz = 2 sz = 2 sz = 2 sz = 2 merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 00000, 1, , 1, , 1, , 1, , 1, 33333) E G M R ) E G M R ) E G M R ) E G M R ) E G M R E S O R E T A X M P E L E S O R E T A X M P E L E S O R E T A X M P E L E S O R E T A X M P E L E S O R E T A X M P E L merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 44444, 5, , 5, , 5, , 5, , 5, 77777) ) ) ) ) E G M R E G M R E G M R E G M R E G M R E O R S E O R S E O R S E O R S E O R S E T A X M P E L E T A X M P E L E T A X M P E L E T A X M P E L E T A X M P E L merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 88888, 9, , 9, , 9, , 9, , 9, 11 11 11 11 11) ) ) ) ) E G M R E O R S E G M R E O R S E G M R E O R S E G M R E O R S E G M R E O R S A E T X A E T X A E T X A E T X A E T X M P E L M P E L M P E L M P E L M P E L merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 12 12 12 12 12, 13, , 13, , 13, , 13, , 13, 15 15 15 15 15) ) ) ) ) E G M R E O R S E G M R E O R S E G M R E O R S E G M R E O R S E G M R E O R S A E T X A E T X A E T X A E T X A E T X E L M P E L M P E L M P E L M P E L M P sz = 4 sz = 4 sz = 4 sz = 4 sz = 4 merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 00000, 3, , 3, , 3, , 3, , 3, 77777) E E G M O R R S ) E E G M O R R S ) E E G M O R R S ) E E G M O R R S ) E E G M O R R S A E T X E L M P A E T X E L M P A E T X E L M P A E T X E L M P A E T X E L M P merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 88888, 11, , 11, , 11, , 11, , 11, 15 15 15 15 15) ) ) ) ) E E G M O R R S E E G M O R R S E E G M O R R S E E G M O R R S E E G M O R R S A E E L M P T X A E E L M P T X A E E L M P T X A E E L M P T X A E E L M P T X sz = 8 sz = 8 sz = 8 sz = 8 sz = 8 merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, merge(a, aux, 00000, 7, , 7, , 7, , 7, , 7, 15 15 15 15 15) A E E E E G L M M O P R R S T X ) A E E E E G L M M O P R R S T X ) A E E E E G L M M O P R R S T X ) A E E E E G L M M O P R R S T X ) A E E E E G L M M O P R R S T X T T T T Tr r r r rac ac ac ac ace of mer e of mer e of mer e of mer e of merge r ge r ge r ge r ge results f esults f esults f esults f esults for bott or bott or bott or bott or bottomup mer omup mer omup mer omup mer omup mergesor gesor gesor gesor gesort t t t t 24Bottomup mergesort: Java implementation public class MergeBU private static void merge(...) / as before / public static void sort(Comparable a) int N = a.length; Comparable aux = new ComparableN; for (int sz = 1; sz N; sz = sz+sz) for (int lo = 0; lo Nsz; lo += sz+sz) merge(a, aux, lo, lo+sz1, Math.min(lo+sz+sz1, N1)); but about 10 slower than recursive, topdown mergesort on typical systems Bottom line. Simple and nonrecursive version of mergesort. 25Mergesort: visualizations topdown mergesort (cutoff = 12) bottomup mergesort (cutoff = 12) 26Natural mergesort Idea. Exploit preexisting order by identifying naturallyoccurring runs. input 1 5 10 16 3 4 23 9 13 2 7 8 12 14 first run 1 5 10 16 3 4 23 9 13 2 7 8 12 14 second run 1 5 10 16 3 4 23 9 13 2 7 8 12 14 merge two runs 1 3 4 5 10 16 23 9 13 2 7 8 12 14 Tradeoff. Fewer passes vs. extra compares per pass to identify runs. 27Timsort Natural mergesort. Use binary insertion sort to make initial runs (if needed). A few more clever optimizations. Tim Peters Intro This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it wink). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N) comparisons needed, and as few as N1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays. In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hardwon measure of memory efficiency. ... Consequence. Linear time on many arrays with preexisting order. Now widely used. Python, Java 7, GNU Octave, Android, …. 28The Zen of Python http://www.python.org/dev/peps/pep0020/ http://westmarch.sjsoft.com/2012/11/zenofpythonposter/ 292.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduComplexity of sorting Computational complexity. Framework to study efficiency of algorithms for solving a particular problem X. Model of computation. Allowable operations. Cost model. Operation count(s). Upper bound. Cost guarantee provided by some algorithm for X. Lower bound. Proven limit on cost guarantee of all algorithms for X. Optimal algorithm. Algorithm with best possible cost guarantee for X. lower bound upper bound Example: sorting. can access information Model of computation: decision tree. only through compares (e.g., Java Comparable framework) Cost model: compares. Upper bound: N lg N from mergesort. Lower bound: Optimal algorithm: 31Decision tree (for 3 distinct keys a, b, and c) a b height of tree = yes no worstcase number of compares code between compares (e.g., sequence of exchanges) b c a c yes no yes no a b c b a c b c a c yes no yes no b c a c b a a c b c a b each leaf corresponds to one (and only one) ordering; (at least) one leaf for each possible ordering 32Comparebased lower bound for sorting Proposition. Any comparebased sorting algorithm must use at least lg ( N ) N lg N compares in the worstcase. Pf. Assume array consists of N distinct values a through a . 1 N Worst case dictated by height h of decision tree. h Binary tree of height h has at most 2 leaves. N different orderings ⇒ at least N leaves. h at least N leaves h no more than 2 leaves 33Comparebased lower bound for sorting Proposition. Any comparebased sorting algorithm must use at least lg ( N ) N lg N compares in the worstcase. Pf. Assume array consists of N distinct values a through a . 1 N Worst case dictated by height h of decision tree. h Binary tree of height h has at most 2 leaves. N different orderings ⇒ at least N leaves. h 2 ≥ leaves ≥ N ⇒ h ≥ lg ( N ) N lg N Stirling's formula 34Complexity of sorting Model of computation. Allowable operations. Cost model. Operation count(s). Upper bound. Cost guarantee provided by some algorithm for X. Lower bound. Proven limit on cost guarantee of all algorithms for X. Optimal algorithm. Algorithm with best possible cost guarantee for X. Example: sorting. Model of computation: decision tree. Cost model: compares. Upper bound: N lg N from mergesort. Lower bound: N lg N. Optimal algorithm = mergesort. First goal of algorithm design: optimal algorithms. 35Complexity results in context Compares Mergesort is optimal with respect to number compares. Space Mergesort is not optimal with respect to space usage. Lessons. Use theory as a guide. Ex. Design sorting algorithm that guarantees ½ N lg N compares Ex. Design sorting algorithm that is both time and spaceoptimal 36Complexity results in context (continued) Lower bound may not hold if the algorithm can take advantage of: The initial order of the input. Ex: insert sort requires only a linear number of compares on partially sorted arrays. The distribution of key values. Ex: 3way quicksort requires only a linear number of compares on arrays with a constant number of distinct keys. stay tuned The representation of the keys. Ex: radix sort requires no key compares — it accesses the data via character/digit compares. 372.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSort countries by gold medals 39Sort countries by total medals 40Sort music library by artist 41Sort music library by song name 42Comparable interface: review Comparable interface: sort using a type's natural order. public class Date implements ComparableDate private final int month, day, year; public Date(int m, int d, int y) month = m; day = d; year = y; … public int compareTo(Date that) natural order if (this.year that.year ) return 1; if (this.year that.year ) return +1; if (this.month that.month) return 1; if (this.month that.month) return +1; if (this.day that.day ) return 1; if (this.day that.day ) return +1; return 0; 43Comparator interface Comparator interface: sort using an alternate order. public interface ComparatorKey public interface ComparatorKey int compare(Key v, Key w) compare(Key v, Key w) compare keys v and w Required property. Must be a total order. string order example Now is the time natural order pre1994 order for digraphs ch and ll and rr is Now the time case insensitive Spanish language café cafetero cuarto churro nube ñoño British phone book McKinley Mackintosh 44Comparator interface: system sort To use with Java system sort: Create Comparator object. Pass as second argument to Arrays.sort(). uses natural order uses alternate order defined by String a; ComparatorString object ... Arrays.sort(a); ... Arrays.sort(a, String.CASEINSENSITIVEORDER); ... Arrays.sort(a, Collator.getInstance(new Locale("es"))); ... Arrays.sort(a, new BritishPhoneBookOrder()); ... Bottom line. Decouples the definition of the data type from the definition of what it means to compare two objects of that type. 45Comparator interface: using with our sorting libraries To support comparators in our sort implementations: Use Object instead of Comparable. Pass Comparator to sort() and less() and use it in less(). insertion sort using a Comparator public static void sort(Object a, Comparator comparator) int N = a.length; for (int i = 0; i N; i++) for (int j = i; j 0 less(comparator, aj, aj1); j) exch(a, j, j1); private static boolean less(Comparator c, Object v, Object w) return c.compare(v, w) 0; private static void exch(Object a, int i, int j) Object swap = ai; ai = aj; aj = swap; 46Comparator interface: implementing To implement a comparator: Define a (nested) class that implements the Comparator interface. Implement the compare() method. public class Student private final String name; private final int section; ... public static class ByName implements ComparatorStudent public int compare(Student v, Student w) return v.name.compareTo(w.name); public static class BySection implements ComparatorStudent public int compare(Student v, Student w) return v.section w.section; this trick works here since no danger of overflow 47Comparator interface: implementing To implement a comparator: Define a (nested) class that implements the Comparator interface. Implement the compare() method. Arrays.sort(a, new Student.ByName()); Arrays.sort(a, new Student.BySection()); Andrews 3 A 6644800023 097 Little Furia 1 A 7660939873 101 Brown Battle 4 C 8740881212 121 Whitman Rohde 2 A 2323435555 343 Forbes Chen 3 A 9918784944 308 Blair Andrews 3 A 6644800023 097 Little Fox 3 A 8842325341 11 Dickinson Chen 3 A 9918784944 308 Blair Furia 1 A 7660939873 101 Brown Fox 3 A 8842325341 11 Dickinson Gazsi 4 B 7660939873 101 Brown Kanaga 3 B 8981229643 22 Brown Kanaga 3 B 8981229643 22 Brown Battle 4 C 8740881212 121 Whitman Rohde 2 A 2323435555 343 Forbes Gazsi 4 B 7660939873 101 Brown 482.2 MERGESORT mergesort ‣ bottomup mergesort ‣ sorting complexity ‣ Algorithms comparators ‣ stability ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduStability A typical application. First, sort by name; then sort by section. Selection.sort(a, new Student.ByName()); Selection.sort(a, new Student.BySection()); Andrews 3 A 6644800023 097 Little Furia 1 A 7660939873 101 Brown Battle 4 C 8740881212 121 Whitman Rohde 2 A 2323435555 343 Forbes Chen 3 A 9918784944 308 Blair Chen 3 A 9918784944 308 Blair Fox 3 A 8842325341 11 Dickinson Fox 3 A 8842325341 11 Dickinson Furia 1 A 7660939873 101 Brown Andrews 3 A 6644800023 097 Little Gazsi 4 B 7660939873 101 Brown Kanaga 3 B 8981229643 22 Brown Kanaga 3 B 8981229643 22 Brown Gazsi 4 B 7660939873 101 Brown Rohde 2 A 2323435555 343 Forbes Battle 4 C 8740881212 121 Whitman Students in section 3 no longer sorted by name. A stable sort preserves the relative order of items with equal keys. 50Stability Q. Which sorts are stable A. Need to check algorithm (and implementation). sorted by time sorted by location (not stable) sorted by location (stable) Chicago 09:00:00 Chicago 09:25:52 Chicago 09:00:00 Phoenix 09:00:03 Chicago 09:03:13 Chicago 09:00:59 Houston 09:00:13 Chicago 09:21:05 Chicago 09:03:13 Chicago 09:00:59 Chicago 09:19:46 Chicago 09:19:32 Houston 09:01:10 Chicago 09:19:32 Chicago 09:19:46 Chicago 09:03:13 Chicago 09:00:00 Chicago 09:21:05 Seattle 09:10:11 Chicago 09:35:21 Chicago 09:25:52 Seattle 09:10:25 Chicago 09:00:59 Chicago 09:35:21 Phoenix 09:14:25 Houston 09:01:10 Houston 09:00:13 no still longer Chicago 09:19:32 Houston 09:00:13 Houston 09:01:10 sorted sorted Chicago 09:19:46 Phoenix 09:37:44 Phoenix 09:00:03 by time by time Chicago 09:21:05 Phoenix 09:00:03 Phoenix 09:14:25 Seattle 09:22:43 Phoenix 09:14:25 Phoenix 09:37:44 Seattle 09:22:54 Seattle 09:10:25 Seattle 09:10:11 Chicago 09:25:52 Seattle 09:36:14 Seattle 09:10:25 Chicago 09:35:21 Seattle 09:22:43 Seattle 09:22:43 Seattle 09:36:14 Seattle 09:10:11 Seattle 09:22:54 Phoenix 09:37:44 Seattle 09:22:54 Seattle 09:36:14 Stability when sorting on a second key 51Stability: insertion sort Proposition. Insertion sort is stable. public class Insertion public static void sort(Comparable a) int N = a.length; for (int i = 0; i N; i++) for (int j = i; j 0 less(aj, aj1); j) exch(a, j, j1); i j 0 1 2 3 4 0 0 B A A A B 1 1 2 3 2 1 0 A B A A B 1 1 2 3 2 2 1 A A B A B 1 2 1 3 2 3 2 A A A B B 1 2 3 1 2 4 4 A A A B B 1 2 3 1 2 A A A B B 1 2 3 1 2 Pf. Equal items never move past each other. 52Stability: selection sort Proposition. Selection sort is not stable. public class Selection public static void sort(Comparable a) int N = a.length; for (int i = 0; i N; i++) i min 0 1 2 int min = i; 0 2 B B A 1 2 for (int j = i+1; j N; j++) 1 1 A B B 2 1 if (less(aj, amin)) min = j; 2 2 A B B 2 1 exch(a, i, min); A B B 2 1 Pf by counterexample. Longdistance exchange can move one equal item past another one. 53Stability: shellsort Proposition. Shellsort sort is not stable. public class Shell public static void sort(Comparable a) int N = a.length; int h = 1; while (h N/3) h = 3h + 1; while (h = 1) for (int i = h; i N; i++) for (int j = i; j h less(aj, ajh); j = h) exch(a, j, jh); h = h/3; h 0 1 2 3 4 B B B B A 1 2 3 4 1 4 A B B B B 1 2 3 4 1 1 A B B B B 1 2 3 4 1 A B B B B 1 2 3 4 1 Pf by counterexample. Longdistance exchanges. 54Stability: mergesort Proposition. Mergesort is stable. public class Merge private static void merge(...) / as before / private static void sort(Comparable a, Comparable aux, int lo, int hi) if (hi = lo) return; int mid = lo + (hi lo) / 2; sort(a, aux, lo, mid); sort(a, aux, mid+1, hi); merge(a, aux, lo, mid, hi); public static void sort(Comparable a) / as before / Pf. Suffices to verify that merge operation is stable. 55Stability: mergesort Proposition. Merge operation is stable. private static void merge(...) for (int k = lo; k = hi; k++) auxk = ak; int i = lo, j = mid+1; for (int k = lo; k = hi; k++) if (i mid) ak = auxj++; else if (j hi) ak = auxi++; else if (less(auxj, auxi)) ak = auxj++; else ak = auxi++; 0 1 2 3 4 5 6 7 8 9 10 A A A B D A A C E F G 1 2 3 4 5 Pf. Takes from left subarray if equal keys. 56Sorting summary inplace stable best average worst remarks 2 2 2 selection ✔ ½ N ½ N ½ N N exchanges use for small N 2 2 insertion ✔ ✔ N ¼ N ½ N or partially ordered tight code; 3/2 shell ✔ N log N c N 3 subquadratic N log N guarantee; merge ✔ ½ N lg N N lg N N lg N stable improves mergesort timsort ✔ N N lg N N lg N when preexisting order holy sorting grail ✔ ✔ N N lg N N lg N 57
Website URL
Comment