/** Contains static methods for sorting, together with the methods 
    that they use. */
public class Sorting  {
   
    
   /** Given h < k, return the position of the minimum value of b[h..k] */
   public static int min(int[] b, int h, int k) {
      int p= h; // will contain index of minimum
      int i= h;
      // {inv: b[p] is the minimum of b[h..i]}
      while (i!= k) {
         i= i+1;
         if (b[i] < b[p])
            {p= i;}
      }
      return p;
   }
   
   /** b[h..k-1] is sorted, and b[k] contains a value
       Sort b[h..k]  */
   public static void insertValue(int[] b, int h, int k) {
      // This algorithm works as follows.
      // 1. b[k] is placed in v.
      // 2. All elements b[k-1], b[p-2], ... that are >= v
      //    are moved up to b[k], b[k-1], ... 
      // 3. v is placed in the vacated position.
      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 < b[i+1..k]
                */
      while ((i != h) && v < b[i-1]) {
         b[i]= b[i-1];
         i= i-1;
      }
      b[i]= v;
   }
   
   /** = index of x in b ---or b.length if x is not in */
   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 && b[i] != x; i++)
          {}
      return b.length;
   }
   
   /** Precondition: b is in ascending order. Return a values
       i that satisfies R: b[i] <= x < b[i+1] */
   public static int binarySearch(int[] b, int x) {
      int i= -1; int j= b.length;
      // {P:b[i] <= x < b[j] and -1 <= i < j <= b.length}
      while (j != i+1) {
         int e= (i+j)/2;
         // {-1 <= i < e < j <= b.length}
         if (b[e] <= 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] <= b[j..]}
      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] <= b[j..]}
      while (j != b.length) {
         // Put into p the index of smallest element of b[j..]
            int p= j; 
            for (int i= j+1; i != b.length; i++) {
               if (b[i] < 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 < j <= k+1  and  b[h..j-1] is sorted
      for (int j= h+1; j <= k; j++) {
         // Sort b[h..j], given that b[h..j-1] is sorted
            insertValue(b,h,j);
      } 
   }
   
}