// Introduction to Algorithms
// Template for Selection.sort() - using where_is_min
// <put your name, login name & student number here>

// don't change the class declaration
public class Selection implements Sorting {

    // don't change the method declaration
    public int[] sort (int[] array) {
	int size = array.length;

	// this is the loop variable
	int sorted_up_to =     ;

	// the precondition for the loop belongs here

	while (       ) {

	    // the loop invariant belongs here

	    // ---------------------------------------------------------
	    // |		|			|		|
	    // ---------------------------------------------------------
	    //  ^		 ^			 ^		 ^
	    //  0		 sorted_up_to		 swap_with	 size


	    // write the body of the loop here

	    // using 
	          = searcher.where_is_min (     );

	    Trace.printarray (         );



	}
	Trace.printarray (       );

	return array;
    }

    // Don't touch the rest of this
    LocatingMinimum searcher;
    public Selection () {
	searcher = new TestLocateMin(); // or LocateMin() to use your own
    }

    // This is also a (possibly obsolete) feature of the Tester.
    int choice = 0;
    public void choice (int c) { choice=c; }
    
    // We'll use this with Merge Sort and Quick Sort.
    // (It is nevertheless needed for "implements Sorting")
    public void cutoff (int n) { }
}

/************************************************************************

When you call the shift() method, how many assignments (to cells
in the array) does it make?

When you run insertion sort on an array of size 5,  approximately
how many assignments to the calls to the shift() method make altogether?

For size 10?  20?  100?   What is the formula for size ?

Suppose you give ALREADY SORTED data to insertion sort, like this:
	run Insertion.java sorted size=5
How many assignments does the shift() method make?

How many positions does the where_to_insert() method need to examine
in the case of sorted data?

Now try with ALMOST SORTED data. See what data the Tester provides with
	run Insertion.java displaced=1
and	run Insertion.java displacedpc=50

How do the numbers of assignments depend on how many displaced values
there are, and how far they are away from where they belong?

Now do the timings for
	check Insertion.java
	check Insertion.java sorted
	check Insertion.java reverse sorted
	check Insertion.java displaced=1
	check Insertion.java displacedpc=1
and insert the formulae here.

Make a concise summary of the results.

This implementation of insertion sort actually takes far longer
than is necessary;  the template in Insertion.java explains why.


 ************************************************************************/