// ------------------
// SelectionSort.java
// ------------------

import java.util.Arrays;

final class SelectionSort {
    /**
     * O(1)   in space
     * O(n^2) in time
     * not stable
     */
    public static void eval (long[] a, int b, int e) {
        assert b <= e;
        if (b == e)
            return;
        final int p = e;
        --e;
        while (b != e) {
            Select.eval(a, b, p);
            ++b;}}}

final class SelectionSortTest { // 4 3 5 2 1
    public static void main (String[] args) {
        System.out.println("SelectionSort.java");

        {
        final long[] a = {5, 4, 3, 2, 1};
        SelectionSort.eval(a, 1, 4);
        assert IsSorted.eval(a, 1, 4);
        assert Arrays.equals(a, new long[] {5, 2, 3, 4, 1});
        }

        for (int i = 0; i != 10; ++i) {
            final long[] a = new long[1000];
            RandomFill.eval(a, 0, a.length);
            SelectionSort.eval(a, 0, a.length);
            assert IsSorted.eval(a, 0, a.length);}

        System.out.println("Done.");}}