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

class SelectionSortProgram
{
    public static void main ( String args[] )
    {
        int a[] = readArray();
        printArray(a);
        selectionSort(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 selection sort
     * algorithm.
     */
    public static void selectionSort ( int a[] )
    {
        for (int i = 0; i < a.length-1; i++ )
        {
            // find location of smallest element remaining
            int spot = findSmallest(a,i,a.length-1);
            
            // swap i with spot
            int temp = a[i];
            a[i] = a[spot];
            a[spot] = temp;
        }
    }
    /**
     * A method to find and return the index of the smallest number
     * in the array from location start-to-end inclusive.
     */
    public static int findSmallest ( int a[], int start, int end )
    {
        int smallestSpot = start;
        for ( int i = start+1; i <= end; i++ )
        {
            if ( a[i] < a[smallestSpot] )
                smallestSpot = i;
        }
        return smallestSpot;
    }
}