/**
* Finds the minimum of A[lo:hi], swaps it with A[lo], recur on A[lo+1:hi].
* Corresponds to splitting the array at the low index after putting the minimum
* element there, sort the two parts, and join the sorted parts.  The join is trivial.
* It's the splitting that requires some work.  As such this selection sort belongs
* to the same family as quick sort.
* @author Dung X. Nguyen - Copyright 1999 - all rights reserved.
* @since 11/28/99
*/
public class SelectionSorter extends ASorter
{
	public final static SelectionSorter Singleton = new SelectionSorter ();

	private SelectionSorter()
	{
	}
	/**
    * Finds the minimum of A[lo:hi] and swaps it with A[lo].
	 * @param A 
	 * @param lo 
	 * @param hi 
	 * @return lo + 1, and A[lo] is the minimum of A[lo:hi].
	 */
	public int split(int[] A, int lo, int hi)
	{
      int s = lo;
      int i = lo + 1;
      // Invariant: A[s] <= A[lo:i-1].
      // Scan A to find minimum:
      while (i <= hi)
      {
         if (A[i] < A[s])
            s = i;
         i++; // Invariant is maintained.
      } // On loop exit: i = hi + 1; also invariant still holds; this makes A[s] the minimum of A[lo:hi].
      // Swapping A[lo] with A[s]:
      int temp = A[lo];
      A[lo] = A[s];
      A[s] = temp;
      // Utility.printArray(A, 0, A.length-1); // for illustration purpose only.
		return lo + 1;
      /*
      // Exercise for the student: write an equivalent for loop.
      */
	}

	/**
	 * @param A  A[lo] is the minimum of A[lo:hi], and A[lo+1:hi] is sorted.
	 * @param lo
	 * @param s  == lo + 1.
	 * @param hi 
	 */
	public void join(int[] A, int lo, int s, int hi)
	{
      // There is nothing to do here!
	}

	public static void main(String[] args)
	{
      int[] A = {99, -34, 0, 5, -7, 0};
      System.out.print ("\nA = ");
      // Utility.printArray(A, 0, A.length-1);
      System.out.println ("\nSelection sorting A...");
      SelectionSorter.Singleton.sort (A, 0, A.length - 1);
      System.out.println ("Sorting done!!!");
      // System.out.print ("\nA = ");
      // Utility.printArray(A, 0, A.length-1);
   }
}