Question? Leave a message!




Two classic sorting algorithms: mergesort and quicksort

Two classic sorting algorithms: mergesort and quicksort
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 2.2 MERGESORT mergesort ‣ bottom-up 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 ‣ bottom-up 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 in-place 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 in-place 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 top-down mergesort result after recursive call 9Mergesort: animation 50 random items algorithm position in order current subarray not in order http://www.sorting-algorithms.com/merge-sort 10Mergesort: animation 50 reverse-sorted items algorithm position in order current subarray not in order http://www.sorting-algorithms.com/merge-sort 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. 13Divide-and-conquer 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 14Divide-and-conquer 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, hidden-line removal, Kendall-tau 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 in-place 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). In-place 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 top-down 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 partially-ordered 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); 20