/**
 * Matt Kretchmar
 * April 1, 2006
 * Program11.java
 * This program uses insertion sort to order an array of integers from
 * smallest to biggest.
 */
import java.util.Scanner;

class Program11
{
    public static void main ( String args[] )
    {
        int a[] = readArray();
        printArray(a);
        insertionSort(a);
        printArray(a);
    }

    /**
     * A method that creates and returns an array of integers.  First the user
     * is prompted for the size of the array and then the entries for the
     * array.
     */
    public static int [] readArray ( )
    {
        Scanner keyboard = new Scanner(System.in);
        
        System.out.println("Enter number of items for array: ");
        int num = keyboard.nextInt();
        int array[] = new int[num];
        
        for ( int i = 0; i < num; i++ )
        {
            System.out.println("Enter item " + i );
            array[i] = keyboard.nextInt();
        }
        return array;
    }
    
    /**
     * A method to print the contents of an integer array on one line.
     */
    public static void printArray ( int a[] )
    {
        for ( int i = 0; i < a.length; i++ )
            System.out.print(a[i] + " ");
        System.out.println();
    }
    
    /**
     * A method to sort an array of integers via the insertion sort
     * algorithm.
     */
    public static void insertionSort ( int a[] )
    {
        // i is the next card to find a spot for
        for (int i = 1; i < a.length; i++ )
        {
            int card = a[i];
            int j = i-1;
            // move cards down the line until we find the correct 
            // spot for the current card.
            while ( j > -1 && a[j] > card )
            {
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = card;
        }
    }
}