6 006 Introduction to Algorithms Lecture 8 Prof Piotr Indyk Menu Sorting Insertion Sort Merge Sort Recurrences Master theorem The problem of sorting Input array A 1 n of numbers Output permutation B 1 n of A such that B 1 B 2 B n e g A 7 2 5 5 9 6 B 2 5 5 7 9 6 How can we do it efficiently Insertion sort A 1 n INSERTION SORT A n for j 2 to n insert key A j into the already sorted sub array A 1 j 1 by pairwise key swaps down to its right position Illustration of iteration j 1 i j A sorted key new location of key n Example of insertion sort 8 2 4 9 3 6 Example of insertion sort 8 2 4 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 Example of insertion sort 8 2 4 9 3 6 2 8 4 9 3 6 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 2 3 4 6 8 9 done Running time n2 e g when input is A n n 1 n 2 2 1 Meet Merge Sort MERGE SORT A 1 n 1 If n 1 done nothing to sort divide and 2 Otherwise recursively sort A 1 n 2 conquer and A n 2 1 n 3 Merge the two sorted sub arrays Key subroutine MERGE Merging two sorted arrays 20 12 13 11 7 9 2 1 Merging two sorted arrays 20 12 13 11 7 9 2 1 1 Merging two sorted arrays 20 12 20 12 13 11 13 11 7 9 7 2 1 2 1 9 Merging two sorted arrays 20 12 20 12 13 11 13 11 7 9 7 2 1 2 1 9 2 Merging two sorted arrays 20 12 20 12 20 12 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 Merging two sorted arrays 20 12 20 12 20 12 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 7 Merging two sorted arrays 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 7 9 Merging two sorted arrays 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 7 9 9 Merging two sorted arrays 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 7 9 9 Merging two sorted arrays 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 7 9 7 7 2 1 2 1 9 2 9 7 9 9 11 Merging two sorted arrays 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 7 2 1 2 1 9 2 9 7 9 9 11 Merging two sorted arrays 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 7 2 1 2 1 9 2 9 7 9 9 11 12 Merging two sorted arrays 20 12 20 12 20 12 20 12 20 12 20 12 13 11 13 11 13 11 13 11 13 11 13 7 9 7 7 2 1 2 1 9 2 9 7 9 9 11 Time Q n to merge a total of n elements linear time 12 Analyzing merge sort MERGE SORT A 1 n 1 If n 1 done 2 Recursively sort A 1 n 2 and A n 2 1 n 3 Merge the two sorted lists T n T n Q 1 if n 1 2T n 2 Q n if n 1 T n Q 1 2T n 2 Q n Recurrence solving Solve T n 2T n 2 cn where c 0 is constant Recursion tree Solve T n 2T n 2 cn where c 0 is constant T n Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn T n 2 T n 2 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn 2 cn 2 T n 4 T n 4 T n 4 T n 4 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn 2 cn 2 cn 4 Q 1 cn 4 cn 4 cn 4 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn 2 cn 2 h lg n cn 4 Q 1 cn 4 cn 4 cn 4 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn cn 2 cn 2 h lg n cn 4 Q 1 cn 4 cn 4 cn 4 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn cn 2 cn 2 h lg n cn 4 Q 1 cn 4 cn 4 cn cn 4 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn h lg n cn 4 Q 1 cn 4 cn 4 cn cn 4 cn cn 2 cn 2 Recursion tree Solve T n 2T n 2 cn where c 0 is constant cn cn cn 2 cn 2 cn 4 cn 4 Q 1 cn 4 cn h lg n cn 4 cn leaves n Q n Recursion tree Solve T n 2T n 2 cn where c 0 is constant …
View Full Document
Unlocking...