reprog_ssort.d

module reprog_ssort;

/**
 * Selection sort.
 *
 * This time actually writing out the various invariants and conditions.
 * We're being FORMAL now, bitches.
 *
 * Compile with the 'paranoid' debug identifier to turn on all the various
 * checks.
 *
 * Returns: array sorted in-place.
 */
T[] selsort(T)(T[] arr)
out(result)
{
    debug(paranoid) assert( isSorted(arr) );
}
body
{
    /*
        Edge cases:

        - Array of length zero,
        - Array of length one.
    */

    if( arr.length <= 1 )
        return arr;

    /*
        Selection sort algorithm (as best I can remember):

        let n = arr.length
        for 0 <= i < n:
            for i+1 <= j < n:
                if arr[j] < arr[i]:
                    swap arr[i], arr[j]

        Any time we find an element smaller than the first element, we swap
        the two.  This ensures, after a single iteration, that the smallest
        value in the array is in the first position.

        We then re-scan the array sans front element (since it is now
        correct).

        Another way of looking at it is that with each iteration, we remove
        one instance of the smallest value from the tail and append it to the
        head.
    */

    auto n = arr.length;

    // Bound: n-i
    // Invariant: isSorted(arr[0..i])
    // Invariant: max(arr[0..i]) <= arr[x] foreach( x ; i+1..n )
    for( size_t i=0; i<n; ++i )
    {
        // Check invariants (if paranoid) :3
        debug(paranoid)
        {
            assert( isSorted(arr[0..i]) );

            auto max_arr_0_i = max(arr[0..i]);
            foreach( e ; arr[i+1..n] )
                assert( max_arr_0_i <= e );
        }

        // Bound: n-j
        // Invariant: arr[i] <= arr[x] foreach( x ; i+1..j )
        for( size_t j=i+1; j<n; ++j )
        {
            // Check invariants
            debug(paranoid)
            {
                if( arr[i+1..j].length > 0 )
                foreach( e ; arr[i+1..j] )
                    assert( arr[i] <= e );
            }

            if( arr[j] < arr[i] )
                swap(arr[i], arr[j]);
        }

        debug(paranoid) foreach( e ; arr[i+1..$] )
            assert( arr[i] <= e );
    }

    // One issue with being formal: the above is now significantly harder to
    // actually *read*.  I can't tell if the code is correct because all the
    // checks obscure the logic.

    return arr;
}

version( Unittest )
{
    import tango.math.random.Random : rand;

    unittest
    {
        alias selsort!(int) ss;

        assert( ss([]) == cast(int[]) [] );
        assert( ss([1]) == [1] );
        assert( ss([1,1]) == [1,1] );
        assert( ss([1,1,1]) == [1,1,1] );
        assert( ss([0,1,2]) == [0,1,2] );
        assert( ss([0,2,1]) == [0,1,2] );
        assert( ss([1,2,0]) == [0,1,2] );
        assert( ss([1,0,2]) == [0,1,2] );
        assert( ss([2,0,1]) == [0,1,2] );
        assert( ss([2,1,0]) == [0,1,2] );
        assert( ss([0,1,1]) == [0,1,1] );
        assert( ss([1,0,1]) == [0,1,1] );
        assert( ss([1,1,0]) == [0,1,1] );
        assert( ss([0,1,2,3,4,5,6,7,8,9]) == [0,1,2,3,4,5,6,7,8,9] );
        assert( ss([9,8,7,6,5,4,3,2,1,0]) == [0,1,2,3,4,5,6,7,8,9] );
        assert( ss([int.min, -1, 0, 1, int.max]) == [int.min, -1, 0, 1, int.max] );
        assert( ss([int.max, 1, 0, -1, int.min]) == [int.min, -1, 0, 1, int.max] );
        assert( ss([42, 9, 17, 54, int.max, 602, -3, 54, int.min, 999, -11])
                == [int.min, -11, -3, 9, 17, 42, 54, 54, 602, 999, int.max] );
        assert( ss([int.min, -11, -3, 9, 17, 42, 54, 54, 602, 999, int.max])
                == [int.min, -11, -3, 9, 17, 42, 54, 54, 602, 999, int.max] );
        assert( ss([int.max, 999, 602, 54, 54, 42, 17, 9, -3, -11, int.min])
                == [int.min, -11, -3, 9, 17, 42, 54, 54, 602, 999, int.max] );

        {
            int[] a1, a2;
            a1 = new int[](10);
            scope(exit) delete a1;
            a2 = new int[](10);
            scope(exit) delete a2;

            for( size_t i=0; i<10; ++i )
            {
                foreach( ref e ; a1 )
                    e = rand.uniform!(int);

                a2 = a1.dup.sort;

                assert( ss(a1) == a2 );
            }
        }
    }
}

/**
 * Take a wild guess.
 */
void swap(T)(ref T a, ref T b)
{
    auto c = a;
    a = b;
    b = c;
}

/**
 * Also really, really deceptive.
 */
bool isSorted(T)(T[] arr)
{
    if( arr.length <= 1 )
        return true;

    for( size_t i=0; i<arr.length-1; ++i )
        if( !( arr[i] <= arr[i+1] ) )
            return false;

    return true;
}

/**
 * You know, I've got NO idea.
 */
T max(T)(T[] arr)
{
    auto r = T.min;
    if( arr.length == 0 )
        return r;

    foreach( e ; arr )
        if( e > r )
            r = e;

    return r;
}

import tango.io.Stdout;

void main()
{
    Stdout("Tests finished.").newline;
}