Question? Leave a message!




ELEMENTARY SORTS

ELEMENTARY SORTS
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 2.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms FOUR TH EDITION shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu2.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSorting problem Ex. Student records in a university. Chen 3 A 9918784944 308 Blair Rohde 2 A 2323435555 343 Forbes Gazsi 4 B 7660939873 101 Brown item Furia 1 A 7660939873 101 Brown Kanaga 3 B 8981229643 22 Brown Andrews 3 A 6644800023 097 Little key Battle 4 C 8740881212 121 Whitman Sort. Rearrange array of N items into ascending order. Andrews 3 A 6644800023 097 Little Battle 4 C 8740881212 121 Whitman Chen 3 A 9918784944 308 Blair Furia 1 A 7660939873 101 Brown Gazsi 4 B 7660939873 101 Brown Kanaga 3 B 8981229643 22 Brown Rohde 2 A 2323435555 343 Forbes 3Sorting applications Library of Congress numbers contacts FedEx packages Hogwarts houses playing cards 4Sample sort client 1 Goal. Sort any type of data. Ex 1. Sort random real numbers in ascending order. seems artificial (stay tuned for an application) public class Experiment java Experiment 10 0.08614716385210452 0.09054270895414829 public static void main(String args) 0.10708746304898642 0.21166190071646818 int N = Integer.parseInt(args0); 0.363292849257276 Double a = new DoubleN; 0.460954145685913 for (int i = 0; i N; i++) 0.5340026311350087 ai = StdRandom.uniform(); 0.7216129793703496 Insertion.sort(a); 0.9003500354411443 for (int i = 0; i N; i++) 0.9293994908845686 StdOut.println(ai); 5Sample sort client 2 Goal. Sort any type of data. Ex 2. Sort strings in alphabetical order. public class StringSorter public static void main(String args) String a = StdIn.readAllStrings(); Insertion.sort(a); for (int i = 0; i a.length; i++) StdOut.println(ai); more words3.txt bed bug dad yet zoo ... all bad yes java StringSorter words3.txt all bad bed bug dad ... yes yet zoo suppressing newlines 6Sample sort client 3 Goal. Sort any type of data. Ex 3. Sort the files in a given directory by filename. java FileSorter . import java.io.File; Insertion.class Insertion.java public class FileSorter InsertionX.class InsertionX.java public static void main(String args) Selection.class Selection.java File directory = new File(args0); Shell.class File files = directory.listFiles(); Shell.java Insertion.sort(files); ShellX.class for (int i = 0; i files.length; i++) ShellX.java StdOut.println(filesi.getName()); 7Total order Goal. Sort any type of data (for which sorting is well defined). A total order is a binary relation ≤ that satisfies: Antisymmetry: if both v ≤ w and w ≤ v, then v = w. Transitivity: if both v ≤ w and w ≤ x, then v ≤ x. Totality: either v ≤ w or w ≤ v or both. Ex. Standard order for natural and real numbers. Chronological order for dates or times. COS 423 COS 333 Alphabetical order for strings. COS 226 COS 217 No transitivity. Rockpaperscissors. COS 126 No totality. PU course prerequisites. violates transitivity violates totality 8Callbacks Goal. Sort any type of data (for which sorting is well defined). Q. How can sort() know how to compare data of type Double, String, and java.io.File without any information about the type of an item's key Callback = reference to executable code. Client passes array of objects to sort() function. The sort() function calls object's compareTo() method as needed. Implementing callbacks. Java: interfaces. C: function pointers. C++: classtype functors. C: delegates. Python, Perl, ML, Javascript: firstclass functions. 9Callbacks: roadmap datatype implementation client public class String implements ComparableString public class StringSorter ... public int compareTo(String b) public static void main(String args) ... String a = StdIn.readAllStrings(); return 1; Insertion.sort(a); ... for (int i = 0; i a.length; i++) return +1; StdOut.println(ai); ... return 0; Comparable interface (built in to Java) sort implementation public static void sort(Comparable a) public interface ComparableItem int N = a.length; public int compareTo(Item that); for (int i = 0; i N; i++) for (int j = i; j 0; j) if (aj.compareTo(aj1) 0) exch(a, j, j1); else break; key point: no dependence on String data type 10Comparable API Implement compareTo() so that v.compareTo(w) Defines a total order. Returns a negative integer, zero, or positive integer if v is less than, equal to, or greater than w, respectively. Throws an exception if incompatible types (or either is null). w v w v v w less than (return 1) equal to (return 0) greater than (return +1) Builtin comparable types. Integer, Double, String, Date, File, ... Userdefined comparable types. Implement the Comparable interface. 11Implementing the Comparable interface Date data type. Simplified version of java.util.Date. public class Date implements ComparableDate private final int month, day, year; public Date(int m, int d, int y) only compare dates to other dates month = m; day = d; year = y; public int compareTo(Date that) 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; 122.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduSelection sort demo In iteration i, find index min of smallest remaining entry. Swap ai and amin. initial 14Selection sort Algorithm. ↑ scans from left to right. Invariants. Entries the left of ↑ (including ↑) fixed and in ascending order. No entry to right of ↑ is smaller than any entry to the left of ↑. ↑ in final order 15Two useful sorting abstractions Helper functions. Refer to data through compares and exchanges. Less. Is item v less than w private static boolean less(Comparable v, Comparable w) return v.compareTo(w) 0; Exchange. Swap item in array a at index i with the one at index j. private static void exch(Comparable a, int i, int j) Comparable swap = ai; ai = aj; aj = swap; 16Selection sort inner loop To maintain algorithm invariants: Move the pointer to the right. i++; in final order ↑ Identify index of minimum entry on right. int min = i; for (int j = i+1; j N; j++) if (less(aj, amin)) in final order ↑ ↑ min = j; Exchange into position. exch(a, i, min); in final order ↑ ↑ 17Selection sort: Java implementation public class Selection public static void sort(Comparable a) int N = a.length; for (int i = 0; i N; i++) int min = i; for (int j = i+1; j N; j++) if (less(aj, amin)) min = j; exch(a, i, min); private static boolean less(Comparable v, Comparable w) / as before / private static void exch(Comparable a, int i, int j) / as before / 18Selection sort: animations 20 random items algorithm position in final order not in final order http://www.sortingalgorithms.com/selectionsort 19Selection sort: animations 20 partiallysorted items algorithm position in final order not in final order http://www.sortingalgorithms.com/selectionsort 20Selection sort: mathematical analysis 2 Proposition. Selection sort uses (N– 1) + (N– 2) + ... + 1 + 0 N / 2 compares and N exchanges. a entries in black i min 0 1 2 3 4 5 6 7 8 9 10 are examined to find the minimum S O R T E X A M P L E 0 6 S O R T E X A M P L E entries in red 1 4 A O R T E X S M P L E are amin 2 10 A E R T O X S M P L E 3 9 A E E T O X S M P L R 4 7 A E E L O X S M P T R 5 7 A E E L M X S O P T R 6 8 A E E L M O S X P T R 7 10 A E E L M O P X S T R 8 8 A E E L M O P R S T X entries in gray are 9 9 A E E L M O P R S T X in final position 10 10 A E E L M O P R S T X A E E L M O P R S T X Trace of selection sort (array contents just after each exchange) Running time insensitive to input. Quadratic time, even if input is sorted. Data movement is minimal. Linear number of exchanges. 212.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduInsertion sort demo In iteration i, swap ai with each larger entry to its left. 23Insertion sort Algorithm. ↑ scans from left to right. Invariants. Entries to the left of ↑ (including ↑) are in ascending order. Entries to the right of ↑ have not yet been seen. in order not yet seen ↑ 24Insertion sort inner loop To maintain algorithm invariants: Move the pointer to the right. i++; ↑ in order not yet seen Moving from right to left, exchange ai with each larger entry to its left. for (int j = i; j 0; j) if (less(aj, aj1)) exch(a, j, j1); else break; ↑ ↑ ↑ ↑ in order not yet seen 25Insertion sort: Java implementation 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; j) if (less(aj, aj1)) exch(a, j, j1); else break; private static boolean less(Comparable v, Comparable w) / as before / private static void exch(Comparable a, int i, int j) / as before / 26Insertion sort: animation 40 random items algorithm position in order not yet seen http://www.sortingalgorithms.com/insertionsort 27Insertion sort: animation 40 reversesorted items algorithm position in order not yet seen http://www.sortingalgorithms.com/insertionsort 28Insertion sort: animation 40 partiallysorted items algorithm position in order not yet seen http://www.sortingalgorithms.com/insertionsort 29Insertion sort: mathematical analysis Proposition. To sort a randomlyordered array with distinct keys, 2 2 insertion sort uses ¼ N compares and ¼ N exchanges on average. Pf. Expect each entry to move halfway back. a i j 0 1 2 3 4 5 6 7 8 9 10 entries in gray S O R T E X A M P L E do not move 1 0 O S R T E X A M P L E 2 1 O R S T E X A M P L E 3 3 O R S T E X A M P L E entry in red 4 0 E O R S T X A M P L E is aj 5 5 E O R S T X A M P L E 6 0 A E O R S T X M P L E 7 2 A E M O R S T X P L E entries in black 8 4 A E M O P R S T X L E moved one position right for insertion 9 2 A E L M O P R S T X E 10 2 A E E L M O P R S T X A E E L M O P R S T X Trace of insertion sort (array contents just after each insertion) 30Insertion sort: trace 31Insertion sort: analysis Best case. If the array is in ascending order, insertion sort makes N – 1 compares and 0 exchanges. A E E L M O P R S T X Worst case. If the array is in descending order (and no duplicates), 2 2 insertion sort makes ½ N compares and ½ N exchanges. X T S R P O M L F E A 32Insertion sort: partiallysorted arrays Def. An inversion is a pair of keys that are out of order. A E E L M O T R X P S TR TP TS RP XP XS (6 inversions) Def. An array is partially sorted if the number of inversions is ≤ c N. Ex 1. A sorted array has 0 inversions. Ex 2. A subarray of size 10 appended to a sorted subarray of size N. Proposition. For partiallysorted arrays, insertion sort runs in linear time. Pf. Number of exchanges equals the number of inversions. number of compares = exchanges + (N – 1) 33Insertion sort: practical improvements Half exchanges. Shift items over (instead of exchanging). Eliminates unnecessary data movement. No longer uses only less() and exch() to access data. A C H H I M N N P Q X Y K B I N A R Y Binary insertion sort. Use binary search to find insertion point. Number of compares N lg N . But still a quadratic number of array accesses. A C H H I M N N P Q X Y K B I N A R Y binary search for first key K 342.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduShellsort overview Idea. Move entries more than one position at a time by hsorting the array. an hsorted array is h interleaved sorted subsequences h = 4 L E E A M H L E P S O L T S X R L M P T E H S S E L O X A E L R h = 13 P H E L L S O R T E X A M S L E Shellsort. Shell 1959 hsort array for decreasing sequence of values of h. P S H L E E input S H E L L S O R T E X A M P L E L L 13sort P H E L L S O R T E X A M S L E (8 additional files of size 1) 4sort L E E A M H L E P S O L T S X R An hsorted fi le is h interleaved sorted fi les 1sort A E E E H L L L M O P R S S T X Shellsort trace (array contents after each pass) 36hsorting demo In iteration i, swap ai with each larger entry h positions to its left.hsorting How to hsort an array Insertion sort, with stride length h. 3sorting an array M O L E E X A S P R T E O L M E X A S P R T E E L M O X A S P R T E E L M O X A S P R T A E L E O X M S P R T A E L E O X M S P R T A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T Why insertion sort Big increments ⇒ small subarray. Small increments ⇒ nearly in order. stay tuned 38Shellsort example: increments 7, 3, 1 input 1sort S O R T E X A M P L E A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T 7sort A E E L O P M S X R T S O R T E X A M P L E A E E L O P M S X R T M O R T E X A S P L E A E E L O P M S X R T M O R T E X A S P L E A E E L M O P S X R T M O L T E X A S P R E A E E L M O P S X R T M O L E E X A S P R T A E E L M O P S X R T A E E L M O P R S X T A E E L M O P R S T X 3sort M O L E E X A S P R T E O L M E X A S P R T result E E L M O X A S P R T A E E L M O P R S T X E E L M O X A S P R T A E L E O X M S P R T A E L E O X M S P R T A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T 39Shellsort: Java implementation public class Shell public static void sort(Comparable a) int N = a.length; int h = 1; 3x+1 increment while (h N/3) h = 3h + 1; // 1, 4, 13, 40, 121, 364, ... sequence while (h = 1) // hsort the array. for (int i = h; i N; i++) insertion sort for (int j = i; j = h less(aj, ajh); j = h) exch(a, j, jh); move to next h = h/3; increment private static boolean less(Comparable v, Comparable w) / as before / private static void exch(Comparable a, int i, int j) / as before / 40Shellsort: visual trace input 40sorted 13sorted 4sorted result 41 Visual trace of shellsortShellsort: animation 50 random items algorithm position hsorted current subsequence other elements http://www.sortingalgorithms.com/shellsort 42Shellsort: animation 50 partiallysorted items algorithm position hsorted current subsequence other elements http://www.sortingalgorithms.com/shellsort 43Shellsort: which increment sequence to use Powers of two. 1, 2, 4, 8, 16, 32, ... No. Powers of two minus one. 1, 3, 7, 15, 31, 63, … Maybe. 3x + 1. 1, 4, 13, 40, 121, 364, … OK. Easy to compute. Sedgewick. 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, … Good. Tough to beat in empirical studies. i i merging of (9 ⨉ 4 ) – (9 ⨉ 2 ) + 1 i i and 4 – (3 ⨉ 2 ) + 1 44Shellsort: intuition Proposition. An hsorted array remains hsorted after gsorting it. 3sort 7sort S O R T E X A M P L E M O L E E X A S P R T M O R T E X A S P L E E O L M E X A S P R T E E L M O X A S P R T M O R T E X A S P L E E E L M O X A S P R T M O L T E X A S P R E A E L E O X M S P R T M O L E E X A S P R T A E L E O X M S P R T A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T A E L E O P M S X R T still 7sorted Challenge. Prove this fact—it's more subtle than you'd think 45Shellsort: analysis Proposition. The order of growth of the worstcase number of compares 3/2 used by shellsort with the 3x+1 increments is N . Property. The expected number of compares to shellsort a randomly ordered array using 3x+1 increments is…. 2 1.3 N compares 2.5 N ln N 0.25 N ln N N 5,000 93K 106K 91K 64K 10,000 209K 230K 213K 158K 20,000 467K 495K 490K 390K 40,000 1022K 1059K 1122K 960K 80,000 2266K 2258K 2549K 2366K Remark. Accurate model has not yet been discovered () 46Why are we interested in shellsort Example of simple idea leading to substantial performance gains. R, bzip2, /linux/kernel/groups.c Useful in practice. Fast unless array size is huge (used for small subarrays). Tiny, fixed footprint for code (used in some embedded systems). Hardware sort prototype. uClibc Simple algorithm, nontrivial performance, interesting questions. Asymptotic growth rate open problem: find a better increment sequence Best sequence of increments Averagecase performance Lesson. Some good algorithms are still waiting discovery. 47Elementary sorts summary Today. Elementary sorting algorithms. algorithm best average worst 2 2 2 selection sort N N N 2 2 insertion sort N N N 3/2 Shellsort (3x+1) N log N N goal N N log N N log N order of growth of running time to sort an array of N items Next week. N log N sorting algorithms (in worst case). 482.1 ELEMENTARY SORTS rules of the game ‣ selection sort ‣ insertion sort ‣ Algorithms shellsort ‣ shuffling ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduHow to shuffle an array Goal. Rearrange array so that result is a uniformly random permutation. all permutations equally likely 50How to shuffle an array Goal. Rearrange array so that result is a uniformly random permutation. all permutations equally likely 51Shuffle sort Generate a random real number for each array entry. Sort the array. useful for shuffling columns in a spreadsheet 0.8003 0.9706 0.9157 0.9649 0.1576 0.4854 0.1419 0.4218 0.9572 52Shuffle sort Generate a random real number for each array entry. Sort the array. useful for shuffling columns in a spreadsheet 0.1419 0.1576 0.4218 0.4854 0.8003 0.9157 0.9572 0.9649 0.9706 53Shuffle sort Generate a random real number for each array entry. Sort the array. useful for shuffling columns in a spreadsheet 0.1419 0.1576 0.4218 0.4854 0.8003 0.9157 0.9572 0.9649 0.9706 Proposition. Shuffle sort produces a uniformly random permutation. assuming real numbers uniformly at random (and no ties) 54War story (Microsoft) Microsoft antitrust probe by EU. Microsoft agreed to provide a randomized ballot screen for users to select browser in Windows 7. http://www.browserchoice.eu appeared last 50 of the time 55War story (Microsoft) Microsoft antitrust probe by EU. Microsoft agreed to provide a randomized ballot screen for users to select browser in Windows 7. Solution Implement shuffle sort by making comparator always return a random answer. Microsoft's implementation in Javascript public int compareTo(Browser that) double r = Math.random(); function RandomSort (a,b) if (r 0.5) return 1; browser comparator return (0.5 Math.random()); if (r 0.5) return +1; (should implement a total order) return 0; 56Knuth shuffle demo In iteration i, pick integer r between 0 and i uniformly at random. Swap ai and ar. 57Knuth shuffle In iteration i, pick integer r between 0 and i uniformly at random. Swap ai and ar. Proposition. FisherYates 1938 Knuth shuffling algorithm produces a uniformly random permutation of the input array in linear time. assuming integers uniformly at random 58Knuth shuffle In iteration i, pick integer r between 0 and i uniformly at random. Swap ai and ar. common bug: between 0 and N – 1 correct variant: between i and N – 1 public class StdRandom ... public static void shuffle(Object a) int N = a.length; for (int i = 0; i N; i++) between 0 and i int r = StdRandom.uniform(i + 1); exch(a, i, r); 59Broken Knuth shuffle Q. What happens if integer is chosen between 0 and N1 A. Not uniformly random instead of 0 and i permutation Knuth shuffle broken shuffle A B C 1/6 4/27 A C B 1/6 5/27 B A C 1/6 5/27 B C A 1/6 5/27 C A B 1/6 4/27 C B A 1/6 4/27 probability of each result when shuffling A, B, C 60War story (online poker) Texas hold'em poker. Software must shuffle electronic cards. How We Learned to Cheat at Online Poker: A Study in Software Security http://www.datamation.com/entdev/article.php/616221 61War story (online poker) Shuffling algorithm in FAQ at www.planetpoker.com for i := 1 to 52 do begin between 1 and 51 r := random(51) + 1; swap := cardr; cardr := cardi; cardi := swap; end; nd nd Bug 1. Random number r never 52 ⇒ 52 card can't end up in 52 place. Bug 2. Shuffle not uniform (should be between 1 and i). 32 Bug 3. random() uses 32bit seed ⇒ 2 possible shuffles. Bug 4. Seed = milliseconds since midnight ⇒ 86.4 million shuffles. Exploit. After seeing 5 cards and synchronizing with server clock, “ The generation of random numbers is too important to be left to chance. ” can determine all future cards in real time. — Robert R. Coveyou 62War story (online poker) Best practices for shuffling (if your business depends on it). Use a hardware randomnumber generator that has passed both the FIPS 1402 and the NIST statistical test suites. Continuously monitor statistic properties: hardware randomnumber generators are fragile and fail silently. Use an unbiased shuffling algorithm. Bottom line. Shuffling a deck of cards is hard 63
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.AlexanderTyler
User Type:
Teacher
Country:
India
Uploaded Date:
21-07-2017