Elementary sorting algorithms

algorithm for sorting numbers in ascending order and bubble sort algorithm with example
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
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 991-878-4944 308 Blair Rohde 2 A 232-343-5555 343 Forbes Gazsi 4 B 766-093-9873 101 Brown item Furia 1 A 766-093-9873 101 Brown Kanaga 3 B 898-122-9643 22 Brown Andrews 3 A 664-480-0023 097 Little key Battle 4 C 874-088-1212 121 Whitman Sort. Rearrange array of N items into ascending order. Andrews 3 A 664-480-0023 097 Little Battle 4 C 874-088-1212 121 Whitman Chen 3 A 991-878-4944 308 Blair Furia 1 A 766-093-9873 101 Brown Gazsi 4 B 766-093-9873 101 Brown Kanaga 3 B 898-122-9643 22 Brown Rohde 2 A 232-343-5555 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. Rock-paper-scissors. 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++: class-type functors. C: delegates. Python, Perl, ML, Javascript: first-class functions. 9Callbacks: roadmap data-type 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(aj-1) 0) exch(a, j, j-1); 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) Built-in comparable types. Integer, Double, String, Date, File, ... User-defined 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.sorting-algorithms.com/selection-sort 19Selection sort: animations 20 partially-sorted items algorithm position in final order not in final order http://www.sorting-algorithms.com/selection-sort 20