/*
 * Created on Aug 4, 2005
 * 
 * CPS 006 - Summer 05
 * Sam Slee
 * Insertion.java
 * 
 * 
 */

public class Insertion {

	//---------------------------------------------------------------------------------
	// Demonstrates the Insertion Sort algorithm.
	public static void main(String[] args) {
		int[] random = {8, 36, 27, 25, 15, 13, 19, 5, 9, 34, 10, 11, 7, 
				33, 6, 30, 14, 3, 18, 22, 32, 16, 1, 20, 24, 
				26, 2, 4, 17, 23, 29, 31, 12, 21, 28, 35};

		int[] reverse = {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25,
				24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13,
				12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		
		int[] input = random;
		int goal = 0;
		
		System.out.println("Array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
		
		System.out.println("\n\nSorting with Insertion Sort \n");
		
		insertionSort(input);
		
		System.out.println("Sorted array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
	}
	
	
	//---------------------------------------------------------------------------------
	// Sorts the given array entries in ascending order
	// using Insertion Sort - O(n^2) time
	public static void insertionSort(int[] input){
		
		int insertIndex;
		int temp;
		
		// starting with array entry indexed at "1" insert each value
		// into the proper spot in the 
		// already sorted portion of the array: input[0..sortedIndex-1]
		// (Note that array entry 0 is sorted to start with because it's only one entry.
		for(int sortedIndex=1; sortedIndex<input.length; sortedIndex++){
			
			// move up to the next value to insert into sorted order
			insertIndex = sortedIndex;
			
			// keep swapping down until we're in the right spot or we run out of room to swap
			while(insertIndex > 0 && input[insertIndex] < input[insertIndex-1]){
				// swapping the values in the array entries
				temp = input[insertIndex-1];
				input[insertIndex-1] = input[insertIndex];
				input[insertIndex] = temp;
				
				// the value I'm inserting is now one index lower
				insertIndex--;
			}
			
		}
	}
}