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; }

## No comments:

## Post a Comment