## Saturday, May 29, 2010

### Selection Sort

The algorithm works as follows:
How it Works;
1) Find the minimum value in the list
2) Swap the minimum item with first item
3) Repeat for all remain positions

Properties;
Worst and average case speed is O(n^2)
Memory is 1
It is Stable (unless you implement it badly)

//compile with g++
#include <iostream>
#include <iomanip>
using namespace std;

void print(int data[], int size);

void selectionSort(int data[], int size)
{
int min;
int tmp;
for(int j = 0; j < size; j++)
{
min = j;
for(int i = j;i < size;i++)
if(data[i] < data[min])
min = i;

if(min != j)
{
tmp = data[min];
data[min] = data[j];
data[j] = tmp;
}
}
}

//test
#define SIZE 20
#define SCRAMBLE(x, y) ((0xa57b & ~y) + ((0x3829 & x) << 1))

bool check(int data[], int size)
{
for(int i = 1; i < size; i++)
if(data[i] < data[i-1])
{
cout << "FAIL!" << endl;
return false;
}
cout << "PASS" << endl;
return true;
}

void print(int data[], int size)
{
for(int i = 0; i < size; i++)
cout << setw(5) << data[i] << " ";
cout << endl;
}

bool test(int data[], int size)
{
print(data, SIZE);
selectionSort(data,SIZE);
print(data, SIZE);
return check(data, SIZE);
}

int main()
{
int data[SIZE];
bool pass = true;

//easy data
data[0] = 1;
for(int i = 0; i < SIZE; i++)
data[i] = SIZE - i;
pass &= test(data, SIZE);

//semi repeated data
data[0] = 1;
for(int i = 1; i < SIZE; i++)
data[i] = SCRAMBLE(i, data[i-1]);
pass &= test(data, SIZE);

//the sort killer!
for(int i = 0; i < SIZE; i++)
data[i] = 5;
pass &= test(data, SIZE);

//and some randoms to catch anything i missed
srand ( time(NULL) );

for(int j = 0; j < 100; j++)
{
for(int i = 0; i < SIZE; i++)
data[i] = (int)((float)(j+1)*((float)rand()/(float)RAND_MAX));
pass &= test(data, SIZE);
}

if(pass)
cout << "ALL PASSED" << endl;
else
cout << "FAILED" << endl;
}