Problem
Implement selection sort
Solution
Select largest element and move it to a[n-1]
Select the second largest element and move it to a[n-2]
and so forth
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Selection sort
Created Data : 18-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
int Max(int* arr, int len){
int m = arr[0];
int idx = 0;
for(int i = 1; i < len; ++i){
if(m < arr[i]){
m = arr[i];
idx = i;
}
}
return idx;
}
void Swap(int& i, int& j)
{
int t = i;
i = j;
j = t;
}
void SelectionSort(int *arr, int len)
{
for(int s = len; s > 1; s--){
int j = Max(arr, s);
Swap(arr[j], arr[s-1]);
}
}
int main(int argc, char* argv[])
{
for(int i = 1; i < 15; ++i){
int* arr = new int[i];
for(int j = 0; j < i; ++ j){
arr[j] = j;
}
random_shuffle(arr, arr + i);
cout << "Test case: " << i << endl;
for(int j = 0; j < i; ++ j){
cout << setw(4) << arr[j];
}
cout << endl;
SelectionSort(arr, i);
cout << "After sorting: " << i << endl;
for(int j = 0; j < i; ++ j){
cout << setw(4) << arr[j];
}
cout << "-----------------------------" << endl;
delete[] arr;
}
return 0;
}
Output
Test case: 1
0
After sorting: 1
0-----------------------------
Test case: 2
0 1
After sorting: 2
0 1-----------------------------
Test case: 3
0 2 1
After sorting: 3
0 1 2-----------------------------
Test case: 4
3 0 2 1
After sorting: 4
0 1 2 3-----------------------------
Test case: 5
2 0 3 1 4
After sorting: 5
0 1 2 3 4-----------------------------
Test case: 6
0 5 4 1 2 3
After sorting: 6
0 1 2 3 4 5-----------------------------
Test case: 7
5 2 6 1 3 0 4
After sorting: 7
0 1 2 3 4 5 6-----------------------------
Test case: 8
1 3 4 0 7 6 2 5
After sorting: 8
0 1 2 3 4 5 6 7-----------------------------
Test case: 9
1 4 6 3 8 7 2 5 0
After sorting: 9
0 1 2 3 4 5 6 7 8-----------------------------
Test case: 10
0 2 7 9 6 5 4 1 3 8
After sorting: 10
0 1 2 3 4 5 6 7 8 9-----------------------------
Test case: 11
2 8 1 4 7 3 10 9 0 6 5
After sorting: 11
0 1 2 3 4 5 6 7 8 9 10-----------------------------
Test case: 12
0 3 10 7 5 8 1 6 4 2 11 9
After sorting: 12
0 1 2 3 4 5 6 7 8 9 10 11-----------------------------
Test case: 13
9 0 7 4 1 12 11 5 2 3 6 8 10
After sorting: 13
0 1 2 3 4 5 6 7 8 9 10 11 12-----------------------------
Test case: 14
5 3 2 4 13 8 10 6 0 12 9 11 1 7
After sorting: 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13-----------------------------
Press any key to continue . . .