``` 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 81 82 83 84 85 86 87 88 89 90 91 ``` ```package algs21; import stdlib.*; public class Shell { // sort the array a[] in ascending order using Shellsort public static > void sort(T[] a) { int N = a.length; // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < N/3) h = 3*h + 1; while (h >= 1) { // h-sort the array for (int i = h; i < N; i++) { for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) { exch(a, j, j-h); } } assert isHsorted(a, h); h /= 3; } 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(T[] a, int i, int j) { if (COUNT_OPS) DoublingTest.incOps (); T 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; } // is the array h-sorted? private static > boolean isHsorted(T[] a, int h) { for (int i = h; i < a.length; i++) if (less(a[i], a[i-h])) 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) { //String[] cards = In.readStrings ("data/cards.txt"); //StdRandom.shuffle (cards); //StdIn.fromFile ("data/tiny.txt"); //StdIn.fromFile ("data/cards.txt"); StdIn.fromFile ("data/words3.txt"); String[] a = StdIn.readAllStrings(); sort(a); show(a); COUNT_OPS = true; DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); } } ```