<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/** Contains static methods for sorting, together with the methods 
 that they use. Included are:
 min, to find the minimum of b[h..k].
 
 insertValue, to insert a value into its sorted position in b[h..k-1].
 
 linearSearch, to find a value in an array.
 
 partition0, used in quicksort, as done in class.
 
 partition, used in quicksort, done a bit more efficiently.
 
 medianOf3, used in quicksort.
 
 copy, to return a copy of b[h..k].
 
 merge, used in mergesort.
 
 binarySearch, binary search in an array.
 
 selectionSort, to sort an array.
 
 selectionSort1, to sort an array.
 
 insertionSort, to sort an array.
 
 mergesort, to sort an array recursively.
 
 quicksort0, the basic quicksort algorithm.
 
 quicksort, quicksort changed to fix inefficiencies.
 
 Dutch National Flag.
 
 toString, to create a String that contains elements of an array
 (alternatively, import java.util.Arrays and use Arrays.toString).
 
 */
public class Sorting  {
    
    /** = the position of the minimum value of b[h..k].
        Precondition: h &lt;= k. */
    public static int min(int[] b, int h, int k) {
        int p= h; 
        int i= h;
        // inv: b[p] is the minimum of b[h..i], i.e.
        //
        //    h-------p------------i---------k
        // b | b[p] is min of this  |    ?    |
        //    --------------------------------
        
        while (i!= k) {
            i= i+1;
            if (b[i] &lt; b[p]) {
              p= i;
            }
        }
        return p;
    }
    
    /** Sort b[h..k]  --put its elements in ascending order.
        Precondition: b[h..k-1] is sorted, and b[k] contains a value. */
    public static void insertValue(int[] b, int h, int k) {
        int v= b[k];
        int i= k;
        /* inv P: (1) Placing v in b[i] makes b[h..k] a
                      permutation of its initial value
         (2) b[h..k] with b[i] removed is initial b[h..k-1]
         (3) v &lt; b[i+1..k]
         */
        while ((i != h) &amp;&amp; v &lt; b[i-1]) {
            b[i]= b[i-1];
            i= i-1;
        }
        b[i]= v;
    }
    
    /** = index of x in b ---or the length of b if x is not in b. */
    public static int linearSearch(int[] b, int x) {
        // invariant: x is not in b[0..i-1]
        int i;
        for (i= 0; i != b.length &amp;&amp; b[i] != x; i= i+1)
        {}
        return i;
    }
    
    
    /** Permute b[h..k] and return integer j satisfying R:&lt;br&gt;&lt;br&gt;
     
          b[h..j-1] &lt;= b[j] = x &lt;= b[j+1..k],&lt;br&gt;&lt;br&gt;
     
     where x stands for the value initially in b[h].
     Precondition: b[h..k] has at least three elements.
     */
    public static int partition0(int[] b, int h, int k) {
        // 
        //          h---------------------------k
        // pre:  b |x|     ?                     |  for some x
        //          -----------------------------
        // 
        //          h-------------j-------------k
        // post: b |   &lt;= x      |x|     &gt;= x    |
        //          -----------------------------
        int j= h;
        int i= k;
        // inv P: b[h..j-1] &lt;= b[j] = x &lt;= b[i+1..k], i.e.
        //  
        //          h---------j-------i------------k
        // post: b |   &lt;= x  |x|  ?    |    &gt;= x    |
        //          --------------------------------
        while (j &lt; i) {
            if (b[j+1] &lt;= b[j]) {
                int temp= b[j]; b[j]= b[j+1]; b[j+1]= temp;
                j= j+1;
            }
            else {
                int temp= b[j+1]; b[j+1]= b[i]; b[i]= temp;
                i= i-1;
            }
        }
        
        return j;
    }
    
    /** Permute b[h..k] and return integer j satisfying R:&lt;br&gt;&lt;br&gt;
     
          b[h..j-1] &lt;= b[j] = x &lt;= b[j+1..k]&lt;br&gt;&lt;br&gt;
     
     where x stands for the value initially in b[h].
     Precondition: b[h..k] has at least three elements. */
    public static int partition(int[] b, int h, int k) {
        int j;
        // Truthify R1: b[h+1..j] &lt;= b[h] = x &lt;= b[j+1..k];
        int i= h+1; j= k;
        // inv P: b[h+1..i-1] &lt;= b[h] = x &lt;= b[j+1..k], i.e.
        //  
        //
        //    h---------i------j----------k
        // b |x| &lt;= x  |    ?   |  &gt;= x    |
        //    -----------------------------
        while (i &lt;= j) {
            if (b[i] &lt; b[h]) {
                i= i+1;
            }
            else if (b[j] &gt; b[h]) {
                j= j-1;
            }
            else {// b[j] &lt; x &lt; b[i]
                int t1= b[i]; b[i]= b[j]; b[j]= t1;
                i= i+1; j= j-1;
            }
        }
        int t= b[h]; b[h]= b[j]; b[j]= t;
        // R
        return j;
    }
    
    /** Permute b[h], b[(h+k)/2], and b[k] to put their median in b[h]. */
    public static void medianOf3(int[] b, int h, int k) {
        int e= (h+k)/2;  // index of middle element of array
        int m;           // index of median
        // Return if b[h] is median; else store index of median in m
        if (b[h] &lt;= b[e]) {
            if (b[h] &gt;= b[k]) return;
            // b[h] is smallest of the three
            if (b[e] &lt;= b[k]) {
                m= e;
            }
            else {
                m= k;
            }
        }
        else {
            if (b[h] &lt;= b[k]) return;
            // b[h] is largest of the three
            if (b[e] &lt;= b[k]) {
                m= k;
            }
            else {
                m= e;
            }
        }
        int t= b[h]; b[h]= b[m]; b[m]= t;
    }
    
    /** = a copy of array segment b[h..k]. */
    public static int[] copy(int[] b, int h, int k) {
        int[] c= new int[k+1-h];
        // inv: b[h..i-1] has been copied to c[0..i-h-1]
        for (int i= h; i != k+1; i= i+1) {
            c[i-h]= b[i];
        }
        return c;
    }
    
    
    /** Sort b[h..k]  --put its elements in ascending order.
        Precondition: Segments b[h..e] and b[e+1..k] are already sorted.
     */
    public static void merge (int b[], int h, int e, int k) {
        int[] c= copy(b,h,e);
        // c is a copy of original b[h..e]
        int i= h; int j= e+1; int m= 0;
        /* inv: b[h..i-1] contains its final, sorted values
         b[j..k] remains to be transferred
         c[m..e-h] remains to be transferred
         */
        for (i= h; i != k+1; i= i+1) {
            if (j &lt;= k &amp;&amp; (m &gt; e-h || b[j] &lt;= c[m])) {
                b[i]= b[j]; j= j+1;
            }
            else {
                b[i]= c[m]; m= m+1;
            }
        }
    }
    
    /** = the index i that satisfies R: b[i] &lt;= x &lt; b[i+1].
        Precondition: b is in non-descending order. */
    public static int binarySearch(int[] b, int x) {
        int i= -1; int j= b.length;
        // inv: b[0..i] &lt;= x &lt; b[j..] and -1 &lt;= i &lt; j &lt;= b.length, i.e.
        
        //          0--------i----------j---------- b.length
        //       b |     &lt;=x  |    ?   |   &gt;x      |
        //          -------------------------------
        while (j != i+1) {
            int e= (i+j)/2;
            // -1 &lt;= i &lt; e &lt; j &lt;= b.length
            if (b[e] &lt;= x) {
                i= e;
            }
            else {
                j= e;
            }
        }
        return i;
    }
    
    /** Sort b --put its elements in ascending order. */
    public static void selectionSort(int[] b) {
        int j= 0;
        // inv P:  b[0..j-1] is sorted and b[0..j-1] &lt;= b[j..], i.e.
        
        //          0---------------j--------------- b.length
        // inv : b |  sorted, &lt;=   |    &gt;=          |
        //          --------------------------------
        
        while (j != b.length) {
            int p= min(b, j, b.length-1);
            // b[p] is minimum of b[j..b.length-1]
            
            // Swap b[j] and b[p]
            int t= b[j]; b[j]= b[p]; b[p]= t;
            j= j+1;
        }
    }
    
    /** Sort b --put its elements in ascending order. */
    public static void selectionSort1(int[] b) {
        int j= 0;
        // inv P: b[0..j-1] is sorted and b[0..j-1] &lt;= b[j..], i.e.
        
        //          0---------------j--------------- b.length
        // inv : b |  sorted, &lt;=   |    &gt;=          |
        //          --------------------------------
        
        while (j != b.length) {
            // Put into p the index of smallest element in b[j..]
            int p= j; 
            for (int i= j+1; i != b.length; i++) {
                if (b[i] &lt; b[p])  {
                    p= i;
                }
            }
            
            // Swap b[j] and b[p]
            int t= b[j]; b[j]= b[p]; b[p]= t;
            j= j+1;
        }
    }
    
    /** Sort b[h..k] --put its elements in ascending order. */
    public static void insertionSort(int[] b, int h, int k) {
        // inv: h &lt;= j &lt;= k+1  and  b[h..j-1] is sorted, i.e.
        
        //          h---------------j--------------k
        // inv : b |  sorted,      |     ?          |
        //          --------------------------------
        
        for (int j= h; j &lt;= k; j= j+1) {
            // Sort b[0..j], given that b[0..j-1] is sorted
            insertValue(b,0,j);
        } 
    }
    
    /** Sort b[h..k]  --put its elements in ascending order. */
    public static void mergeSort(int[] b, int h, int k) {
        if (h &gt;= k) {
            return;
        }
        
        int e= (h+k)/2;
        mergeSort(b, h, e);   // Sort b[h..e]
        mergeSort(b, e+1, k); // Sort b[e+1..k]
        merge(b, h, e, k);    // Merge the 2 segments
    }
    
    /** Sort b[h..k]  --put its elements in ascending order. */
    public static void quickSort0(int[] b, int h, int k) {
        if (k+1-h &lt; 2) {
            return;
        }
        
        int j= partition(b,h,k);
        // b[h..j-1] &lt;= b[j] &lt;= b[j+1..k]
        quickSort0(b,h,j-1);
        quickSort0(b,j+1,k);
    }
    
    /** Sort b[h..k]  --put its elements in ascending order. */
    public static void quickSort(int[] b, int h, int k) {
        tailRecursionLoop: while (true) {         
            if (k+1-h &lt; 10) {
                insertionSort(b,h,k);
                return;
            }
            medianOf3(b,h,k);
            
            // b[h] is between b[(h+k)/2] and b[k]
            int j= partition(b,h,k);
            // b[h..j-1] &lt;= b[j] &lt;= b[j+1..k], i.e.
            //
            //    h---------j---------k
            // b |   &lt;= x  |x|  &gt;= x   |   for some x
            //    ---------------------
            if (j-h &lt;= k-j) {
                quickSort(b,h,j-1);
                // quicksort(b,j+1,k);
                h= j+1;
                continue tailRecursionLoop;
            }
            else {
                quickSort(b,j+1,k);
                // quicksort(b,h,j-1);
                k= j-1;
                continue tailRecursionLoop;
            }
        } // tailRecursionLoop
    }
    
    /** Swap the values of b so that the negative ones are
     first, then the 0's, and finally the positive ones.
     In the original problem, the negative values are red
     balls, 0's are white balls, positive values are blue balls*/
    public static void DutchNationalFlag(int[] b) {
        //        0------------------------------------ b.length
        // pre: b|              ?                      |
        //        -------------------------------------
        // 
        //        0------------------------------------ b.length
        // post:b|   &lt;0    |    = 0     |    &gt;0        |
        //        -------------------------------------
        
        int h= 0;
        int k= 0;
        int t= b.length-1;
        
        //        0-------h-------k------t------------- b.length
        // inv :b|  &lt;0   |  = 0  |   ?    |    &gt;0      |
        //        -------------------------------------
        
        while (k &lt;= t) {
            if (b[k] &lt; 0) {
                int temp= b[k]; b[k]= b[h]; b[h]= temp;
                h= h+1;  k= k+1;
            }
            else if (b[k] == 0) {
                k= k+1;
            }
            else {
                int temp= b[k]; b[k]= b[t]; b[t]= temp;
                t= t-1; 
            }
        }
        
    }
    
    /** = values of b, separated by ", " and with
     the whole list delimited by "[" and "]".
     */
    public static String toString(int[] b) {
        String res= "[";
        // inv: res contains b[0..k-1], with "[" at
        //      beginning and values separated by ", "
        for (int k= 0; k != b.length; k= k+1) {
            if (k != 0)
                res= res + ", ";
            res= res + b[k];
        }
        return res + "]";
    }
    
}
</pre></body></html>