``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 ``` ```// Exercise 2.1.24, 2.1.25 (Solution published at http://algs4.cs.princeton.edu/) package algs21; import stdlib.*; public class XInsertionX { public static > void sort(T[] a) { int N = a.length; // put smallest element in position to serve as sentinel for (int i = N-1; i > 0; i--) if (less(a[i], a[i-1])) exch(a, i, i-1); // insertion sort with half-exchanges for (int i = 2; i < N; i++) { T v = a[i]; int j = i; while (less(v, a[j-1])) { a[j] = a[j-1]; j--; } a[j] = v; } assert isSorted(a); } /* ********************************************************************* * Helper sorting functions ***********************************************************************/ // is v < w ? private static > boolean less(T v, T w) { if (COUNT_OPS) DoublingTest.incOps (); return v.compareTo(w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { if (COUNT_OPS) DoublingTest.incOps (); Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /* ********************************************************************* * Check if array is sorted - useful for debugging ***********************************************************************/ private static > boolean isSorted(T[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; } // print array to standard output private static void show(T[] a) { for (T element : a) { StdOut.println(element); } } // test code private static boolean COUNT_OPS = false; public static void main(String[] args) { StdIn.fromString ("S O R T E X A M P L E"); //StdIn.fromFile ("data/tiny.txt"); StdIn.fromFile ("data/words3.txt"); String[] a = StdIn.readAllStrings(); Insertion.sort(a); show(a); COUNT_OPS = true; DoublingTest.run (2000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); DoublingTest.run (2000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); DoublingTest.run (2000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); } } ```