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}