/**
    FILE:           InsertionSort.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    Functions:      InsertionSort()--------> creates an array, may be presorted.
                    createAndSort()--> creates an array and sorts the
                                       array, may print array after.
                    insert()---------> insert the next element in the previous
                                       sorted subsequence, a subarray.
                    print()----------> print the entire array.
                    sort()-----------> sort the array using either iterative 
                                       or recursive insertion sort.
                    sortIteratively()--> self-explanatory.
                    sortRecursively()--> self-explanatory.
                    
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/

package sorts;

class InsertionSort {
    public static final int MAX_VALUE = 1000000;
    private int a[];
    
    public InsertionSort(int arraySize, boolean presorted){
        a = new int[arraySize];
        
        if (presorted){
            //  sorted array
            for (int i=0; i < a.length; i++){
                a[i] = i;
            }
        }
        else {
            //  seed the array elements randomly
            for (int i=0; i < a.length; i++){
                a[i] = (int)(Math.random()*MAX_VALUE);   
            }
        }
    }
    
    public static void createAndSort(int arraySize, boolean presorted,
                                     boolean printIt, boolean iterative){
        long timeBegan = 0;
        long timeFinished = 0; 
        long timeNeeded = 0;
        
        //  create an array of integers
        InsertionSort aInsertionSorter = new InsertionSort(arraySize, presorted);

        //  time the sorting algorithm
        timeBegan = System.currentTimeMillis();
     
        aInsertionSorter.sort(iterative);
        
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Sorting the array of size " + arraySize +
                            " took = " + timeNeeded + " milliseconds.");       

        if (printIt){
            System.out.println("\n\t Now print the array elements:\n" +
                               "\t Note if the array is too large, " +
                               "the elements may run off the screen!\n");
            aInsertionSorter.print();
        }
    }
    
  public void print(){
    for (int i = 0; i < a.length;i++){
        System.out.println(" a[" + i + "] = " + a[i] + "\n");
        }
 }
 
 public void sortIteratively(){
    int temp = 0;
    int previousIndex = 0;
    boolean found = false;
 
    //  temp saves the value stored in a[i] in the ith iteration,
    //  thus creating a hole in the array for storage,
    //  this permits backward copying/swapping from previous index
    //  to (previous index - 1), and move the hole to previous index
    
    for (int i = 1; i < a.length; i++){
        temp = a[i];    //  pull the ith element "out"
        found = false;  //  assuming that we did not find the right place
                        //  to insert the element that we pulled out
        previousIndex = i-1;                   
        
        while ((previousIndex >= 0)&&(found == false)){
            //  while there are still elements to the left of the
            //  current position, and we have not found the right place
            if (a[previousIndex] > temp){
                //  swapping the larger elements back one position
                a[previousIndex+1] = a[previousIndex];
                previousIndex--;    //  keep going forward, to the left
            }
            else { 
                found = true; 
                }
        }
        
        a[previousIndex+1] = temp;  
        //  we found it, let's copy the pulled element back
        }
 }    
 
 /* Earlier I had the two function calls in the else reversed;
    I was able to realize this after reading the following document
    in HMTL format:
    http://www.mathcs.richmond.edu/~hubbard/cmsc221/lectures/
    11.InsertionSort.pdf
    however, the PDF cannot be displayed */
 public void sortRecursively(int a[], int lastAccessibleIndex){
    //  only one element in the array, hence obviously sorted
    if (lastAccessibleIndex == 0) {return;}
    else {  //  otherwise sort the previous subarray, then insert the
            //  last element, the (n-1)th, into the sorted array.
        sortRecursively(a, lastAccessibleIndex-1);
        insert(a[lastAccessibleIndex], a, lastAccessibleIndex);
    }
}
    
 public void insert(int temp, int a[], int arraySize){
    int previousIndex = arraySize-1;
    boolean found = false;  
 
    while ((previousIndex >= 0)&&(found == false)){
        //  while there are still elements to the left of the
        //  current position, and we have not found the right place
        if (a[previousIndex] > temp){
            //  swapping the larger elements back one position
            a[previousIndex+1] = a[previousIndex];
            previousIndex--;    //  keep going forward, to the left
        }
        else { 
            found = true; 
            }
    }
        
    a[previousIndex+1] = temp;  
        //  we found it, let's copy the pulled element back
    }   
 
 public void sort(boolean iteratively){
    
    if (iteratively){
        sortIteratively();}
    else {
        sortRecursively(a, a.length-1);}
 }
}