/** This program is intended to be used with the book "Java 7 -- What Do You Want To Do?"
 * by Steven P. Warr and is distributed free of charge and without and expectations of remuneration.
 * Chapter ALG   NOTE all program names begin with the title of the chapter in which
 * they are intended to be used.   Copyright 2010 Steven P. Warr All rights reserved
 */
//alg 07
import java.util.*; 
import java.io.*; 
public class Alg07 
{
   public static void main(String[ ] args) throws IOException
    {
    	Scanner infile = new Scanner(new File("alg05.data"));
		Scanner keyIn = new Scanner(System.in);
		int x = 0;
		int totalNumber = 0;
		totalNumber = infile.nextInt(); //First number in data file is the 
										//is the count.
		int [] number = new int[totalNumber];										
		System.out.println("Original array" + " " + totalNumber);
		while (infile.hasNext())
		     {
				number[x] = infile.nextInt();
				System.out.println(number[x]);
				x++;
			}	
		insertionSort(number);
		System.out.println("\nSorted array of " + totalNumber+ "\n");
		for(x = 0; x< number.length; x++)
			System.out.println(number[x]);
		
		
     }		
public static void insertionSort(int [] list)
  {
       int next = 0;
       int y = 0;
       for (int x = 1; x< list.length; x++) //Assume the first element is 
            {                               //is a sorted list.
		 		next = list[x];
		 		y = x;
		 		while (y > 0 && list [y - 1] > next) //Find the insertion point
		 		    {					
		                list[y] = list[y - 1]; // Move all elements up one
		                y --;
		            }    
		        list[y] = next;          //Insert the element    
	        }

 }	
}