//
// Modified by Rimon Barr for cs100 on 28 March 2001.
//   Simply added the demo code.
//

/****************************************************************
 *
 * File name: InsertionSort.java
 *
 * A class to sort an array of integers using an insertion sort
 *   algorithm. Returns the elements of the original array,
 *   but in ascending order.
 *
 * Precondition: Every element of the array a has a value and
 *   the array has at least one value.
 *
 * Based on SelectionSort, Display 6.13/page 426.
 *
 * Written by: Lew Rakocy
 * email address: LRakocy@devrycols.edu
 * Date: 7/3/99
 * Last changed: 9/1/2000 Prologue: email address & Based on.
 *
 ***************************************************************/
public class InsertionSort
{
    public static void sort(int[] a)
    {
        //elements are read from the original array one at a time
        //and inserted into temp array in their proper order.
        //After all the elements have been processed temp contains
        //the original array's elements in ascending order.
        int[] temp = new int[a.length];//max size same as input array
        int sizeOfTemp = 0;//Initial size is zero
        int next;//next element to insert
        int insertIndex;//insertion point into temp

        //First element must go to first position in temp
        //Assumes the array has at least one value.
        temp[0] = a[0];
        sizeOfTemp++;//temp now has one element
        //Must find insertion point for remaining values
        //before inserting them.
        for(int i = 1; i < a.length; i++)
        {
           next = a[i];
           insertIndex = findInsertIndex(next, temp, sizeOfTemp);
           sizeOfTemp++;
           moveElements(insertIndex, temp, sizeOfTemp);
           temp[insertIndex] = next;
        }
        //Done: copy temp to a
        for(int i = 0; i < a.length; i++)
           a[i] = temp[i];
     }

    private static int findInsertIndex(int value, int[] array, int tempSize)
    {
        int i;//Need exit value after loop
        for( i = 0; i <tempSize; i++)
        {
            if(value < array[i])
               return(i);//insertion point found
        }
        return(i);//insertion point is after last element
    }

    private static void moveElements(int lowIndex, int[] array, int highIndex)
    {
       for(int i = highIndex - 1; i > lowIndex; i--)
       {
          array[i] = array[i-1];//move element down one place
       }
    }

    public static void printArray(int[] a) {
      if(a==null || a.length<1) return;
      System.out.print(a[0]);
      for(int i=1; i<a.length; i++)
        System.out.print(", "+a[i]);
      System.out.println();
    }

    public static void demo(int[] a) {
      System.out.print("Array:  ");
      printArray(a);
      sort(a);
      System.out.print("Sorted: ");
      printArray(a);
    }

    public static void main(String[] args) {
      demo(new int[] {1,20,2,30,3,10});
      demo(new int[] {-1,-2,13});
      demo(new int[] {0});
    }
}