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}