/**
* Finds the minimum of A[lo:hi], swaps it with A[lo], recur on A[lo+1:hi].
* Correponds to splitting the array at the low index after putting the minimum
* element there, sort the two parts, and join the sorted part.  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 CSelectionSorter extends ACompareSorter {
    public static final CSelectionSorter Singleton = new CSelectionSorter();
    private CSelectionSorter() {
    }
    /**
    * 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].
     */
    protected int split(IOrdered[] 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].compare(A[s]) == IOrdered.LESS)
                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]:
        IOrdered temp = A[lo];
        A[lo] = A[s];
        A[s] = temp;
        return lo + 1;
    }

    /**
     * @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
     */
    protected void join(IOrdered[] A, int lo, int s, int hi) {
    }
}