001// Exercise 2.1.24, 2.1.25 (Solution published at http://algs4.cs.princeton.edu/)
002package algs21;
003import stdlib.*;
004
005public class XInsertionX {
006
007        public static <T extends Comparable<? super T>> void sort(T[] a) {
008                int N = a.length;
009
010                // put smallest element in position to serve as sentinel
011                for (int i = N-1; i > 0; i--)
012                        if (less(a[i], a[i-1])) exch(a, i, i-1);
013
014                // insertion sort with half-exchanges
015                for (int i = 2; i < N; i++) {
016                        T v = a[i];
017                        int j = i;
018                        while (less(v, a[j-1])) {
019                                a[j] = a[j-1];
020                                j--;
021                        }
022                        a[j] = v;
023                }
024                assert isSorted(a);
025        }
026
027
028        /* *********************************************************************
029         *  Helper sorting functions
030         ***********************************************************************/
031
032        // is v < w ?
033        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
034                if (COUNT_OPS) DoublingTest.incOps ();
035                return v.compareTo(w) < 0;
036        }
037
038        // exchange a[i] and a[j]
039        private static void exch(Object[] a, int i, int j) {
040                if (COUNT_OPS) DoublingTest.incOps ();
041                Object swap = a[i];
042                a[i] = a[j];
043                a[j] = swap;
044        }
045
046
047        /* *********************************************************************
048         *  Check if array is sorted - useful for debugging
049         ***********************************************************************/
050        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
051                for (int i = 1; i < a.length; i++)
052                        if (less(a[i], a[i-1])) return false;
053                return true;
054        }
055
056        // print array to standard output
057        private static <T> void show(T[] a) {
058                for (T element : a) {
059                        StdOut.println(element);
060                }
061        }
062
063        // test code
064        private static boolean COUNT_OPS = false;
065        public static void main(String[] args) {
066                StdIn.fromString ("S O R T E X A M P L E");
067                //StdIn.fromFile ("data/tiny.txt");
068                //StdIn.fromFile ("data/cards.txt");
069                //StdIn.fromFile ("data/words3.txt");
070
071                String[] a = StdIn.readAllStrings();
072                //StdRandom.shuffle (a);
073                //show(a);
074                //StdOut.println ("----------------");
075                sort(a);
076                show(a);
077
078                COUNT_OPS = true;
079                DoublingTest.run (2000, 6, N -> ArrayGenerator.integerRandomUnique (N),      (Integer[] x) -> sort (x));
080                //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
081                //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
082        }
083}