001// Exercise 2.5.27 (Solution published at http://algs4.cs.princeton.edu/) 002package algs21; 003import stdlib.*; 004import java.util.Comparator; 005/* *********************************************************************** 006 * Compilation: javac Insertion.java 007 * Execution: java Insertion < input.txt 008 * Dependencies: StdOut.java StdIn.java 009 * Data files: http://algs4.cs.princeton.edu/21sort/tiny.txt 010 * http://algs4.cs.princeton.edu/21sort/words3.txt 011 * 012 * Sorts a sequence of strings from standard input using insertion sort. 013 * 014 * % more tiny.txt 015 * S O R T E X A M P L E 016 * 017 * % java Insertion < tiny.txt 018 * A E E L M O P R S T X [ one string per line ] 019 * 020 * % more words3.txt 021 * bed bug dad yes zoo ... all bad yet 022 * 023 * % java Insertion < words3.txt 024 * all bad bed bug dad ... yes yet zoo [ one string per line ] 025 * 026 *************************************************************************/ 027 028public class Insertion { 029 030 // use natural order and Comparable interface 031 public static <T extends Comparable<? super T>> void sort(T[] a) { 032 int N = a.length; 033 for (int i = 0; i < N; i++) { 034 for (int j = i; j > 0 && less(a[j], a[j-1]); j--) { 035 exch(a, j, j-1); 036 } 037 //assert isSorted(a, 0, i); 038 } 039 //assert isSorted(a); 040 } 041 042 // use a custom order and Comparator interface - see Section 3.5 043 public static <T> void sort(T[] a, Comparator<? super T> c) { 044 int N = a.length; 045 for (int i = 0; i < N; i++) { 046 for (int j = i; j > 0 && less(c, a[j], a[j-1]); j--) { 047 exch(a, j, j-1); 048 } 049 assert isSorted(a, c, 0, i); 050 } 051 assert isSorted(a, c); 052 } 053 054 // return a permutation that gives the elements in a[] in ascending order 055 // do not change the original array a[] 056 public static <T extends Comparable<? super T>> int[] indexSort(T[] a) { 057 int N = a.length; 058 int[] index = new int[N]; 059 for (int i = 0; i < N; i++) 060 index[i] = i; 061 062 for (int i = 0; i < N; i++) 063 for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--) 064 exch(index, j, j-1); 065 066 return index; 067 } 068 069 /* ********************************************************************* 070 * Helper sorting functions 071 ***********************************************************************/ 072 073 // is v < w ? 074 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 075 if (COUNT_OPS) DoublingTest.incOps (); 076 return (v.compareTo(w) < 0); 077 } 078 079 // exchange a[i] and a[j] 080 private static <T> void exch(T[] a, int i, int j) { 081 if (COUNT_OPS) DoublingTest.incOps (); 082 T swap = a[i]; 083 a[i] = a[j]; 084 a[j] = swap; 085 } 086 087 088 // is v < w ? 089 private static <T> boolean less(Comparator<? super T> c, T v, T w) { 090 if (COUNT_OPS) DoublingTest.incOps (); 091 return (c.compare(v, w) < 0); 092 } 093 094 // exchange a[i] and a[j] (for indexSort) 095 private static void exch(int[] a, int i, int j) { 096 if (COUNT_OPS) DoublingTest.incOps (); 097 int swap = a[i]; 098 a[i] = a[j]; 099 a[j] = swap; 100 } 101 102 /* ********************************************************************* 103 * Check if array is sorted - useful for debugging 104 ***********************************************************************/ 105 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 106 return isSorted(a, 0, a.length - 1); 107 } 108 109 // is the array sorted from a[lo] to a[hi] 110 private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) { 111 for (int i = lo + 1; i <= hi; i++) 112 if (less(a[i], a[i-1])) return false; 113 return true; 114 } 115 116 private static <T> boolean isSorted(T[] a, Comparator<? super T> c) { 117 return isSorted(a, c, 0, a.length - 1); 118 } 119 120 // is the array sorted from a[lo] to a[hi] 121 private static <T> boolean isSorted(T[] a, Comparator<? super T> c, int lo, int hi) { 122 for (int i = lo + 1; i <= hi; i++) 123 if (less(c, a[i], a[i-1])) return false; 124 return true; 125 } 126 127 // print array to standard output 128 private static <T> void show(T[] a) { 129 StdOut.println(java.util.Arrays.toString(a)); 130 } 131 132 // test code 133 private static boolean COUNT_OPS = false; 134 public static void main(String[] args) { 135 StdIn.fromString ("S O R T E X A M P L E"); 136 //StdIn.fromFile ("data/tiny.txt"); 137 //StdIn.fromFile ("data/cards.txt"); 138 //StdIn.fromFile ("data/words3.txt"); 139 140 String[] a = StdIn.readAllStrings(); 141 //StdRandom.shuffle (a); 142 //show(a); 143 //StdOut.println ("----------------"); 144 sort(a); 145 show(a); 146 147 COUNT_OPS = true; 148 DoublingTest.run (2000, 6, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 149 //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 150 //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 151 } 152}