001package algs21; 002import stdlib.*; 003 004public class Shell { 005 006 // sort the array a[] in ascending order using Shellsort 007 public static <T extends Comparable<? super T>> void sort(T[] a) { 008 int N = a.length; 009 010 // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... 011 int h = 1; 012 while (h < N/3) h = 3*h + 1; 013 014 while (h >= 1) { 015 // h-sort the array 016 for (int i = h; i < N; i++) { 017 for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) { 018 exch(a, j, j-h); 019 } 020 } 021 assert isHsorted(a, h); 022 h /= 3; 023 } 024 assert isSorted(a); 025 } 026 027 028 029 /* ********************************************************************* 030 * Helper sorting functions 031 ***********************************************************************/ 032 033 // is v < w ? 034 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 035 if (COUNT_OPS) DoublingTest.incOps (); 036 return (v.compareTo(w) < 0); 037 } 038 039 // exchange a[i] and a[j] 040 private static <T> void exch(T[] a, int i, int j) { 041 if (COUNT_OPS) DoublingTest.incOps (); 042 T swap = a[i]; 043 a[i] = a[j]; 044 a[j] = swap; 045 } 046 047 048 /* ********************************************************************* 049 * Check if array is sorted - useful for debugging 050 ***********************************************************************/ 051 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 052 for (int i = 1; i < a.length; i++) 053 if (less(a[i], a[i-1])) return false; 054 return true; 055 } 056 057 // is the array h-sorted? 058 private static <T extends Comparable<? super T>> boolean isHsorted(T[] a, int h) { 059 for (int i = h; i < a.length; i++) 060 if (less(a[i], a[i-h])) return false; 061 return true; 062 } 063 064 // print array to standard output 065 private static <T> void show(T[] a) { 066 for (T element : a) { 067 StdOut.println(element); 068 } 069 } 070 071 // test code 072 private static boolean COUNT_OPS = false; 073 public static void main(String[] args) { 074 //String[] cards = In.readStrings ("data/cards.txt"); 075 //StdRandom.shuffle (cards); 076 077 //StdIn.fromFile ("data/tiny.txt"); 078 //StdIn.fromFile ("data/cards.txt"); 079 StdIn.fromFile ("data/words3.txt"); 080 081 String[] a = StdIn.readAllStrings(); 082 sort(a); 083 show(a); 084 085 COUNT_OPS = true; 086 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 087 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 088 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 089 } 090 091}