# Selection Sort

Selection sort performs the following steps:

1) Starting at index 0, search the entire array to find the smallest value

2) Swap the smallest value found with the value at index 0

3) Repeat steps 1 & 2 starting from the next index

In other words, we’re going to find the smallest element in the array, and put it in the first position. Then we’re going to find the next smallest element, and put it in the second position. This process will be repeated until we run out of elements.

Here is an example of this algorithm working on 5 elements. Let’s start with a sample array:

{ 30, 50, 20, 10, 40 }

First, we find the smallest element, starting from index 0:

{ 30, 50, 20, **10**, 40 }

We then swap this with the element at index 0:

{ **10**, 50, 20, **30**, 40 }

Now that the first element is sorted, we can ignore it. Consequently, we find the smallest element, starting from index 1:

{ 10, 50, **20**, 30, 40 }

And swap it with the element in index 1:

{ 10, **20**, **50**, 30, 40 }

Find the smallest element starting at index 2:

{ 10, 20, 50, **30**, 40 }

And swap it with the element in index 2:

{ 10, 20, **30**, **50**, 40 }

Find the smallest element starting at index 3:

{ 10, 20, 30, 50, **40** }

And swap it with the element in index 3:

{ 10, 20, 30, **40**, **50** }

Finally, find the smallest element starting at index 4:

{ 10, 20, 30, 40, **50** }

And swap it with the element in index 4 (which doesn’t do anything):

{ 10, 20, 30, 40, **50** }

Done!

{ 10, 20, 30, 40, 50 }

#include <algorithm> // for swap #include <iostream> int main() { using namespace std; const int nSize = 5; int anArray[nSize] = {30, 50, 20, 10, 40}; cout << "Before sorting: "; for(int j = 0; j < nSize; j++) cout << anArray[j] << " "; cout << endl; //step through each element of the array for(int nStartIndex = 0; nStartIndex < nSize; nStartIndex++) { //nSmallestIndex is the index of the smallest element //we've encountered so far int nSmallestIndex = nStartIndex; //Search through every element starting at nStartIndex+1 for(int nCurrentIndex = nStartIndex + 1; nCurrentIndex < nSize; nCurrentIndex++) { if(anArray[nCurrentIndex] < anArray[nSmallestIndex]) //store the index in nSmallestIndex nSmallestIndex = nCurrentIndex; } //Swap our start element with our smallest element swap(anArray[nStartIndex], anArray[nSmallestIndex]); } cout << "After sorting: "; for(int j = 0; j < nSize; ++j) cout << anArray[j] << " " ; cout << endl; }

Source: Selection Sort