New version page

Princeton COS 226 - Elementary Sorts

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more

This preview shows page 1-2 out of 7 pages.

View Full Document
View Full Document

End of preview. Want to read all 7 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

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
Loading Unlocking...
Login

Join to view Elementary Sorts and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Elementary Sorts and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?