Below is the syntax highlighted version ofInsertionX.javafrom§2.1 Elementary Sorts.
/****************************************************************************** * Compilation: javac InsertionX.java * Execution: java InsertionX < input.txt * Dependencies: StdOut.java StdIn.java * Data files:https://algs4.cs.princeton.edu/21elementary/tiny.txt *https://algs4.cs.princeton.edu/21elementary/words3.txt * * Sorts a sequence of strings from standard input using an optimized * version of insertion sort that uses half exchanges instead of * full exchanges to reduce data movement.. * * % more tiny.txt * S O R T E X A M P L E * * % java InsertionX < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java InsertionX < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************//** * The {@code InsertionX} class provides static methods for sorting * an array using an optimized version of insertion sort (with half exchanges * and a sentinel). *<p> * In the worst case, this implementation makes ~ 1/2<em>n</em><sup>2</sup> * compares to sort an array of length<em>n</em>. * So, it is not suitable for sorting large arrays * (unless the number of inversions is small). *<p> * This sorting algorithm is stable. * It usesΘ(1) extra memory (not including the input array). *<p> * For additional documentation, see *<ahref="https://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of *<i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * *@author Robert Sedgewick *@author Kevin Wayne */publicclassInsertionX{// This class should not be instantiated.privateInsertionX(){}/** * Rearranges the array in ascending order, using the natural order. *@param a the array to be sorted */publicstaticvoidsort(Comparable[] a){int n= a.length;// put smallest element in position to serve as sentinelint exchanges=0;for(int i= n-1; i>0; i--){if(less(a[i], a[i-1])){exch(a, i, i-1); exchanges++;}}if(exchanges==0)return;// insertion sort with half-exchangesfor(int i=2; i< n; i++){Comparable v= a[i];int j= i;while(less(v, a[j-1])){ a[j]= a[j-1]; j--;} a[j]= v;}assertisSorted(a);}/*************************************************************************** * Helper sorting functions. ***************************************************************************/// is v < w ?privatestaticbooleanless(Comparable v,Comparable w){return v.compareTo(w)<0;}// exchange a[i] and a[j]privatestaticvoidexch(Object[] a,int i,int j){Object swap= a[i]; a[i]= a[j]; a[j]= swap;}/*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/privatestaticbooleanisSorted(Comparable[] a){for(int i=1; i< a.length; i++)if(less(a[i], a[i-1]))returnfalse;returntrue;}// print array to standard outputprivatestaticvoidshow(Comparable[] a){for(int i=0; i< a.length; i++){ StdOut.println(a[i]);}}/** * Reads in a sequence of strings from standard input; insertion sorts them; * and prints them to standard output in ascending order. * *@param args the command-line arguments */publicstaticvoidmain(String[] args){ String[] a= StdIn.readAllStrings(); InsertionX.sort(a);show(a);}}