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
025                assert isSorted(a);
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 void exch(Object[] a, int i, int j) {
041                if (COUNT_OPS) DoublingTest.incOps ();
042                Object 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        // print array to standard output
058        private static <T> void show(T[] a) {
059                for (T element : a) {
060                        StdOut.println(element);
061                }
062        }
063
064        // test code
065        private static boolean COUNT_OPS = false;
066        public static void main(String[] args) {
067                StdIn.fromString ("S O R T E X A M P L E");
068                //StdIn.fromFile ("data/tiny.txt");
069                //StdIn.fromFile ("data/cards.txt");
070                //StdIn.fromFile ("data/words3.txt");
071
072                String[] a = StdIn.readAllStrings();
073                //StdRandom.shuffle (a);
074                //show(a);
075                //StdOut.println ("----------------");
076                sort(a);
077                show(a);
078
079                COUNT_OPS = true;
080                DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
081                //DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
082                //DoublingTest.run (2000, 10, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
083        }
084}