package Sorter;

/**
 * A concrete sorter that uses the Selection Sort technique.
 */
public class SelectionSorter extends ASorter
{

	/**
	 * The constructor for this class.
	 * @param iCompareOp The comparison strategy to use in the sorting.
	 */
	public SelectionSorter(AOrder iCompareOp)
	{
		super(iCompareOp);
	}
	/**
	 * Splits A[lo:hi] into A[lo:s-1] and A[s:hi] where s is the returned value of this function.
	 * This method places the "smallest" value in the lo position and splits it off.
	 * @param A the array A[lo:hi] to be sorted.
	 * @param lo the low index of A.
	 * @param hi the high index of A.
	 * @return lo+1 always
	 */
	protected int split(Object[] 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 (aOrder.lt(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]:
      Object temp = A[lo];
      A[lo] = A[s];
      A[s] = temp;
		return lo + 1;
 	}

	/**
	 * Joins sorted A[lo:s-1] and sorted A[s:hi] into A[lo:hi].
	 * This method does nothing.  The sub-arrays are already in proper order.
	 * @param A A[lo:s-1] and A[s:hi] are sorted.
	 * @param lo the low index of A.
	 * @param s 
	 * @param hi the high index of A.
	 */
	protected void join(Object[] A, int lo, int s, int hi)
	{
	}
}