public class Demo {
    
    
    /** = the first occurrence of v in b[h..k-1]
          (= k if v is not in b[h..k]) */
    public static int linearSearch(int v, int[] b, int h, int k) {
        int i= h;
        // invariant v is not in b[h..i-1]
        while (i != k && v != b[i]) {
            i= i+1;
        }
        
        // R: v is not in b[h..i-1] and
        // (i = k or v = b[k]
        return i;
    }
    
    /** = the first occurrence of v in b[h..k-1]
          (= k if v is not in b[h..k]) */
    public static int linearSearch1(int v, int[] b, int h, int k) {
        int i;
        // invariant v is not in b[h..i-1]
        for (i= h; i != k && v != b[i]; i= i+1) {
        }
        
        // R: v is not in b[h..i-1] and
        // (i = k or v = b[k]
        return i;
    }

    /** = index of minimum of b[h..k].
        Precondition: b[h..k] is not empty. */
    public static int min(int[] b, int h, int k) {
        int m= h;
        //invariant: b[m] is the minimum of b[h..t-1]
        for (int t= h+1; t <= k; t= t+1) {
            if (b[t] < b[m]) {
                m= t;
            }
        }
        //R: b[m] is the minimum of b[h..k+1-1]
        return m;
    }
    
    /** = index i that satisfies b[0..i] <= v < b[i..].
          Precondition: b is in ascending order */
    public static int binarySearch(int v, int[] b) {
        int i= 0; 
        int j= b.length;
        //invariant: b[0..i <= v < b[j..]
        while (i+1 != j ) {
            int e= (i+j)/2;
            // 0 <= i < e < j <= b.length
            if (b[e] <= v) i= e;
           else j= e;
        }
        //R: b[0..i] <= v < b[i+1..]
        return i;
    }
    
    /** = elements of b, delimited by [] and separated by ", " */
    public static String toString(int[] b) {
        String res= "[";
        for (int i= 0; i != b.length; i= i+1) {
            if (i != 0) res= res + ", ";
            res= res + b[i];
        }
        return res + "]";
    }
    
    /** Dutch national Flag problem. 
        Swap elements of b so that red
        calls (#1) are first, then white balls (#2),
        and finally blue balls (#3).
        Precondition: b contains only the numbers
        1, 2, and 3 */
    public static void DutchFlag(int[] b) {
        int n= b.length; // number of values in array b
        int h= 0; int k= 0; int t= n;
        //invariant: 0 >= h <= k <= t <= n
        //  b[0..h-1] red, b[h..k-1] white, b[t..n-1] blue
        while (k != t) {
            if (b[k] == 1) {//red
                // Swap b[h] and b[k]
                int temp= b[h]; b[h]= b[k]; b[k]= temp;
                h= h+1; k= k+1;
            }
            else if (b[k] == 2) {//white
                k= k+1;
            }
            else {//blue
                t= t-1;
                //Swap b[k] and b[t];
                int temp= b[k]; b[k]= b[t]; b[t]= temp;
            }
        }
        
        //R: b[0..h-1] red, b[h..k-1] white, b[k..n-1] blue
    }
    
    /** Let x be the value initially in b[h], and assume h <= k.
        Swap elements of b[h..k] and return a value j so that
        
          b[h..j-1] <= x = b[j] <= b[j+1..k]
     */
    public static int partition(int[] b, int h, int k) {
        int j= h; int t= k+1;
        // invariant: b[h..j-1] <= x = b[j] <= b[t..k]
        while (t != j+1) {
            if (b[j+1] <= b[j]) {
                // Swap b[j] and b[j+1]
                int temp= b[j]; b[j]= b[j+1]; b[j+1]= temp;
                j= j+1;
            }
            else {
                t= t-1;
                // Swap b[t] and b[j+1]
                int temp= b[t]; b[t]= b[j+1]; b[j+1]= temp;
            }
        }
        //R: b[h..j-1] <= x = b[j] <= b[j+1..k]
        return j; 
    }
        
    /** Sort b[h..k] using selection sort */
    public static void selectionSort(int[] b) {
        
        //inv: b[0..k-1] is sorted and
        //     b[0..k-1 <= b[k..]
        for (int k= 0; k != b.length; k= k+1) {
            int m= min(b, k, b.length-1);
            // Swap b[k] and b[m]
            int temp= b[k]; b[k]= b[m]; b[m]= temp;
        }
        
        //R: b[0..b.length-1] is sorted
    }
    
        /** Sort b[h..k] using insertion sort */
    public static void insertionSort(int[] b) {
        
        //inv: b[0..k-1] is sorted 
        for (int k= 0; k != b.length; k= k+1) {
            pushDown(b, k);
        }
        
        //R: b[0..b.length-1] is sorted
    }

    
    /** Precondition: b[0..h-1] is sorted
        Swap b[0..h] so that it is sorted */
    public static void pushDown(int[] b, int h) {
        int k= h;
        while (k != 0 && b[k] < b[k-1]) {
            // Swap b[k] and b[k-1]
            int temp= b[k]; b[k]= b[k-1]; b[k-1]= temp;
            k= k-1;
        }
    }
    
    
    
    /** Sort b[h..k] */
    public static void quickSort(int[] b, int h, int k) {
        if (h == k+1 || h == k)
            return;
        
        int j= partition(b, h, k);
        quickSort(b, h, j-1);
        quickSort(b, j+1, k);
    }
}