/**
* Implementation of insertion sort
* @author gtowell
* created: April 10, 2020
*/
public class Insertion extends SortBase{
    
    @Override
    public void sortInPlace(int[] rdm)
    {
        insertionSortIP(rdm, 0, rdm.length);
    }
    
    /**
    * Actually do the insertion soft on the specified portion of the array
    * @param rdm the array to be sorted
    * @param startLoc starting location
    * @param endLoc ending location
    */
    public void insertionSortIP(int[] rdm, int startLoc, int endLoc) {
        for (int i=(startLoc+1); i<endLoc; i++)
        {
            int tgt = rdm[i];
            int j;
            // find the spot
            for (j=startLoc; j<i; j++)
            {
                if (rdm[j]>tgt) break;
            }
            // make a space
            for (int k=i; k>j; k--)
            {
                rdm[k]=rdm[k-1];
            }
            rdm[j]=tgt;
        }
        //System.out.println(cnt);
    }
    
    /**
    * A slightly faster implementation of insertion sort.
    * This version combines the j and k loops of insertionSortIP into a single loop
    * @param arr the array to be implemeted.
    */
    public void insertionSort2(int arr[]) 
    { 
        int n = arr.length; 
        for (int i = 1; i < n; i++) { 
            int key = arr[i]; 
            int j = i - 1; 
            
            /* Move elements of arr[0..i-1], that are 
            greater than key, to one position ahead 
            of their current position */
            while (j >= 0 && arr[j] > key) { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = key; 
        } 
    } 

    public void insertionSort3(int arr[]) {
        for (int i=1; i<arr.length; i++) {
            int j;
            for (j=i-1; j>=0; j--) {
                if (arr[j] > arr[i])
                    break;
            }
        }
    }
    
}