// Sorting.java
// [comment block]

public class Sorting
{
    // This method takes in a comparable array and sorts it,
    //      in ASCENDING ORDER, with SELECTION SORT,
    // using the compareTo() method defined for the class.
    // It keeps track of how many comparisons it has to make,
    // and returns the final count.
    // Algorithm:
    // 1. Make a copy of array a and call it c.
    // 2. For each entry of c, find the next smallest entry in a,
    //    and copy it into c. Each time you call compareTo(),
    //    increment the number of comparisons made.
    // 3. Copy c's contents back into a.
    // 4. Return the number of comparisons.  
    public static int selectionSort(Comparable[] a)
    {
    }

    // This method takes in a comparable array and sorts it,
    //      in ASCENDING ORDER, with BUBBLE SORT,
    // using the compareTo() method defined for the class.
    // It keeps track of how many comparisons it has to make,
    // and returns the final count.
    // Algorithm: (double loop)
    // 1. Loop over the array n times (n is the length of the array)
    //    a. Loop down the array. If the current entry is larger
    //       than the next entry, swap them.  Each time you call compareTo(),
    //       increment the number of comparisons made.
    // 2. Return the number of comparisons.  
    public static int bubbleSort(Comparable[] a)
    {
    }

    // This method takes in a comparable array and sorts it,
    //      in ASCENDING ORDER, with INSERTION SORT,
    // using the compareTo() method defined for the class.
    // It keeps track of how many comparisons it has to make,
    // and returns the final count.
    public static int insertionSort(Comparable[] a)
    {
	int numComps = 0;
	// Make a copy of the array to insert into  
	Comparable[] c = new Comparable[a.length];

	// Now sort 'a' into 'c'
	// For each element in a, insert it in the right place in c 
	for (int i=0; i<a.length; i++)
	{
	    int j;
	    for (j=0; j<i; j++)
	    {
		// Increment comparisons
		numComps++;
		// if c[j] >= a[i], a[i] belongs here, so break
		if (c[j].compareTo(a[i]) > -1) break;
	    }
	    // Move everything from j on, down one
	    for (int k=i; k>j; k--)
	    {	
		c[k] = c[k-1];
	    }
	    // Now put the ith element in at j
	    c[j] = a[i];

	    // INVARIANT: array c is now sorted from 0 to i.
	}
	// Now copy c back into a, since it's sorted
	for (int i=0; i<a.length; i++) a[i] = c[i];

	return numComps;
    }

}