package insertionsort;

public class InsertionSort {

    /**
     * Move element in data that is at position i to
     * position j after first creating a "hole" at j by
     * moving elements to the right.
     */
    public static void insert( int [] data, int i, int j ) {
        // hold onto a copy of the value that we are
	// going to move
	int temp = data[i];

        // make a hole in the array at the right spot
	// by moving elements to the right
        for( int k = i; k > j; k-- ) {
	    data[k] = data[k - 1];
	} // for

	// put the value we wanted to move
	// into the right spot
	data[j] = temp;
    } // insert( int [], int, int )

    /**
     * In a search from right to left that begins
     * at position i, look for the position of the last
     * element in array that is greater than the one at position i
     */
    public static int findPos( int [] data, int i ) {
	int j = i;
	while( j > 0 && data[j - 1] > data[i] ) {
	    j--;
	} // while

	return j;
    } // findPos( int [], int )

    public static void sort( int [] data ) {
	for( int i = 0; i < data.length; i++ ) {
	    print( data );
	    int j = findPos( data, i );
	    System.out.println( "move element at position " + i +
				" to position " + j +
				"( move the " + data[i] + 
				" to where the " + data[j] + " is)" );
	    insert( data, i, j );
	} // for
    } // sort( int [] )

    public static void print( int [] data ) {
	for( int n : data ) {
	    System.out.print( n + " " );
	} // for
	System.out.println();
    } // print( int [] )

    public static void main( String [] args ) {
	int [] data = { 5, 3, 2, 4, 1, 7, 6, 8 };

	sort( data );

	print( data );
    } // main( String [] )
} // InsertionSort