001package algs21;
002import stdlib.*;
003
004public class Selection {
005
006        // selection sort
007        public static <T extends Comparable<? super T>> void sort(T[] a) {
008                int N = a.length;
009                for (int i = 0; i < N; i++) {
010                        int min = i;
011                        for (int j = i+1; j < N; j++) {
012                                if (less(a[j], a[min])) min = j;
013                        }
014                        if (i!=min)
015                                exch(a, i, min);
016                        //assert isSorted(a, 0, i);
017                }
018                //assert isSorted(a);
019        }
020
021        /* *********************************************************************
022         *  Helper sorting functions
023         ***********************************************************************/
024
025        // is v < w ?
026        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
027                if (COUNT_OPS) DoublingTest.incOps ();
028                return (v.compareTo(w) < 0);
029        }
030
031        // exchange a[i] and a[j]
032        private static <T> void exch(T[] a, int i, int j) {
033                if (COUNT_OPS) DoublingTest.incOps ();
034                T swap = a[i];
035                a[i] = a[j];
036                a[j] = swap;
037        }
038
039
040        /* *********************************************************************
041         *  Check if array is sorted - useful for debugging
042         ***********************************************************************/
043
044        // is the array a[] sorted?
045        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
046                return isSorted(a, 0, a.length - 1);
047        }
048
049        // is the array sorted from a[lo] to a[hi]
050        private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) {
051                for (int i = lo + 1; i <= hi; 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}