package sort;

/**
 * Insertion Sort Algorithm
 * @author Winston Prakash
 */
public class InsertionSort<E extends Comparable<E>> {
     private transient E[] dataArray;
     private transient E[] sortedArray;
    int dataSize;
    /** Creates a new instance of InsertionSort */
    public InsertionSort(E[] data) {
        dataArray = data;
        sortedArray = (E[]) new Comparable[data.length];
        System.arraycopy(data, 0, sortedArray, 0, data.length);
        dataSize = sortedArray.length;
    }
    
    /**
     * Scan the inner array  (left side array) backward and move the value from the current index
     * of outer array and insert it at the correct place in the already
     * sorted inner array (loop invariant) if it is less than values in the inner array.
     */
    public void sort(){
        for (int out = 1; out< dataSize; out++){
            E temp = sortedArray[out];
            
            for (int in = out;  in > 0; in--){
               if (sortedArray[in-1].compareTo(temp) > -1){
                  sortedArray[in] =  sortedArray[in - 1];
                  sortedArray[in - 1] = temp;
               } 
            }
        }
    }
    public void displayData(){
        System.out.println("\nArray sorting using Insertion Sort Algorithm");
        System.out.println("\nUnsorted Array");
        for (int i =0; i< dataArray.length; i++){
            System.out.print(dataArray[i] + "  ");
        }
        System.out.println("\nSorted Array");
        for (int i =0; i< sortedArray.length; i++){
            System.out.print(sortedArray[i] + "  ");
        }
        System.out.println();
    }
}