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 java.util.Arrays.sort(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, 6, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 081 //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 082 //DoublingTest.run (2000, 6, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 083 } 084}