Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos2263.1 Elementary SortsReference: Chapter 6, Algorithms in Java, 3rd Edition, Robert Sedgewick.2Basic TermsEx: student record in a University.Sort: rearrange sequence of objects into ascending order.3Rules of the GameGoal. Write robust sorting library that can sort any type of data intosorted order using the data type's natural order.Callbacks.! Client passes array of objects to sorting routine.! Sorting routine calls back object's comparison function as needed.Implementing callbacks.! Java: interfaces.! C: function pointers.! C++: functors.! C#: delegates.! Lisp: first class functions.clientdata typesorting libraryconstructcallbackscomparesort4Comparable InterfaceComparable interface. Class is required to provide a method compareToso that v.compareTo(w)returns:! A negative integer if v is less than w.! A positive integer if v is greater than w.! Zero if v is equal to w.Consistency. It is the programmer's responsibility to ensure thatcompareTo specifies a total order.! If a < b and b < c, then a < c. [transitivity]! Exactly one holds: a < b, b < a, a = b. [trichotomy]Built-in comparable types: String, Double, Integer, Date, File.User-defined types: easy to implement Comparable interface.5Implementing the Comparable Interface: Datepublic class Date implements Comparable<Date> { private int month, day, year; public Date(int m, int d, int y) { month = m; day = d; year = y; } public int compareTo(Date b) { Date a = this; if (a.year < b.year ) return -1; if (a.year > b.year ) return +1; if (a.month < b.month) return -1; if (a.month > b.month) return +1; if (a.day < b.day ) return -1; if (a.day > b.day ) return +1; return 0; }}only compare datesto other dates6Two Array Sorting AbstractionsHelper functions. Refer to data only through two operations.! Less. Is v less than w ?! Exchange. Swap objects in array at index i with the one at index j.private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0;}private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; }7Check if SortedExample usage. Is the input sorted?public static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true;}Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Insertion Sort9Insertion SortInsertion sort.! Scans from left to right.! Element to right of ! are not touched.! Invariant: elements to the left of ! are in ascending order.! Inner loop: repeatedly swap element ! with element to its left.in order not yet seen!in order not yet seen!!!!10Insertion Sort Example11Insertion Sort: Java Implementationpublic 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(a[j], a[j-1])) exch(a, j, j-1); else break;}Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Selection Sort13Selection SortSelection sort.! ! scans from left to right.! Elements to the left of ! are fixed and in ascending order.! No element to left of ! is larger than any element to its right.in final order!14Selection Sort Example15Selection Sort Inner Loop: Maintaining the InvariantSelection sort inner loop.! Identify index of minimum item.! Exchange into position.int min = i;for (int j = i+1; j < N; j++) if (less(a[j], a[min])) min = j;exch(a, i, min);!!!!!16Selection Sort: Java Implementationpublic class Selection { private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } private static void exch(Comparable[] a, int i, int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } public static void sort(Comparable a[]) { for (int i = 0; i < a.length; i++) { int min = i; for (int j = i+1; j < a.length; j++) if (less(a[j], a[min])) min = j; exch(a, i, min); } }}selection sort a[]swap references a[i] and a[j]is v less than w?17import java.io.File;public class Files { public static void main(String[] args) { File directory = new File(args[0]); File[] files = directory.listFiles(); Selection.sort(files); for (int i = 0; i < files.length; i++) System.out.println(files[i]); }}% java Files .Insertion.classInsertion.javaInsertionX.classInsertionX.javaSelection.classSelection.javaShell.classShell.javaShellX.classShellX.javaindex.htmlSelection Sort: Sample ApplicationList files. List the files in the current directory, sorted by file name.Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Analysis19Performance for Randomly Ordered FilesSelection.! Always search through right part.! (1 + 2 + ... + N) " N2 / 2 compares." N exchanges.Insertion.! Each element moves halfway back.! (1 + 2 + ... + N) / 2 " N2 / 4 compares. " N2 / 4 exchanges.Bottom line: insertion, selection similar.Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Sorting Challenges21Sorting Challenge 1Problem: sort a file of huge records with tiny keys.Ex: reorganizing your MP3 files.Which sorting method to use?1. system sort2. insertion sort3. selection sort23Sorting Challenge 2Problem: sort a huge randomly-ordered file of small records.Ex: process transaction records for a phone company.Which sorting method to use?1. system sort2. insertion sort3. selection sort25Sorting Challenge 3Problem: sort a huge number of tiny files (each file is independent)Ex: daily customer transaction records.Which sorting method to use?1. system sort2. insertion sort3. selection sort27Sorting Challenge 4Problem: sort a huge file that is already almost in order.Ex: re-sort a huge database after a few changes.Which sorting method to use?1. system sort2. insertion sort3. selection sort29Visual Sorting Puzzle1. Insertion sort.2. Selection sort.3. Bubble
View Full Document
Unlocking...