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}