/*   Quiz #07     Name: _________________________________  Section: ___ */




/* Tear off the top strip  to turn in   */
/************************************************************/

/* Instructions: modify the code to ... (details will be given in class).*/
/* makrk your changes directly on this sheet. */
 
/** Insertion Sort and related methods
 */
public class Sorts {
    
    /** Creates a new instance of Sorts */
    public Sorts() {
    }
    
    /** Sort an entire array.
     */
    public void insertionSort (int[] array) {
        
        for (int i = 0; i < array.length-1; i++) {
            
            insertValue(array, i, array[i+1]);          
        }
    }
    
    /** Insert a new value into an array.  Before the method executes,
     * array values in position 0 to n are assumed to be in order.
     * After the method executes, values in 0 through n + 1 must be in order.
     * There is no change to the values in n+2 through length-1.
     * Note that the value at position n+1 is wiped out.
     * n must be less than the array length -1 (ie.e., n+1 is <= the length.*/
    
    public void insertValue(int[] array, int n, int newValue) {
        
        /* The "new sorted area" is array positions 0 to n+1.
        /*Start filling from at the right end of the new sorted area.*/
        int vacantPos = n + 1;
        boolean found = false; /*says "we don't know where the new value belongs"*/
        
        while (vacantPos > 0 && found == false) {
            
            if (newValue >= array[vacantPos-1]) {
                
                //since we're moving right to left, this must be the FIRST
                //time we've seen newValue >= array[pos]
                found = true; //stop the while loop before pos changes again.
            } else {
                //fill the vacant spot with the value to the left
                array[vacantPos] = array[vacantPos -1];
                
                vacantPos--;
            }
        }
        array[vacantPos] = newValue; // the new value belongs at vacantPos
    }
    
    
    
    private boolean testInsert(int[] original, int n, int newValue, int[] modified) {
        insertValue(original, n, newValue);
        boolean OK = true;
        for (int p = 0; p <= n+1; p++) {
            if (original[p] != modified[p]) {
                OK = false;
                break;
            }
        }
        return OK;
    }
    
    private void dumpArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print("  " + array[i]);
            
        }
        System.out.println();
    }
    private boolean isSorted(int[] array, int n) {
        boolean retVal = true;
        for (int i = 0; i < n; i++) {
            if (array[i] > array[i+1] ) {
                retVal = false;
                break;
            }
        }
        return retVal;            
    }

    private int minArray(int[] array) {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }

    
    public static void main(String[] args) {
        Sorts sTester = new Sorts();
        int[] testa1 = new int[] {10, 20};
        for (int pos = 0; pos < 1; pos++) {
            int newval = 7;
            boolean result = sTester.testInsert(testa1, 0, newval, 
                        new int[] {7, 10});
            if (!result) {
                System.out.println("Test failed. pos=" + pos + " newval=" + newval);
                sTester.dumpArray(testa1);
            }
        }
        sTester.insertionSort(new int[] {10, 9, 8});
        int[] testa2 = new int[] {10, 20, -10, -29, 3, 8, 2, 1, 14};
        for (int t = 1; t < 1000; t++) {
            int newv = (int) (Math.random() * 5000 + -2500);
            testa2[3] = newv;
        int premin = sTester.minArray(testa2);
        sTester.insertionSort(testa2);
        //sTester.dumpArray(testa2);
        assert premin == sTester.minArray(testa2);
        assert premin == testa2[0];
        System.out.println( " " + premin);
        }
        System.out.println("tests done");
        
    }

        
    
}