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

// don't change the class declaration
public class Insertion 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		 insert_at		 sorted_up_to	 size


	    // write the body of the loop here

	    // using 
	          = searcher.where_to_insert (     );

	    Trace.printarray (         );

	    shifter.shift  (      );


	}
	Trace.printarray (       );

	return array;
    }

    // Don't touch the rest of this
    SearchingToInsert searcher;
    Shifting shifter;
    public Insertion0 () {
	shifter  = new TestShift();   // or Shift() to use your own code
	searcher = new TestSearchToInsert(); // or ILinear()
    }

    // 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.


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