Skip to content

Instantly share code, notes, and snippets.

@DanielKeep
Created May 21, 2010 06:47
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save DanielKeep/408553 to your computer and use it in GitHub Desktop.
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment