Algorithms: Lesson 8: Selection Sort

Lesson 8: Selection Sort

In this algorithms video tutorial, we explain how to perform the Selection Sort algorithm on an array of sortable entries. The basic idea of the selection sort is that we set each successive entry to the next smallest value in the array.

The selection sort algorithm is very simple. First, run through the entries in the array and find the smallest one. Then swap it with the first element in the array so that the smallest entry is in the first position. Next, run through the remaining entries to find the next smallest of the remaining entries and swap it into the second position. Continue this procedure of filling the next position with the next smallest entry for the rest of the array. This finishes the algorithm and sorts the array.

In addition to the array of entries that we are sorting, we use an integer to store the index of the smallest of the remaining entries. This integer index is initialized to the value of the next entry that we are filling and is set to a new index whenever we find an entry with a smaller value. By doing this, we set its value to the index of the smallest of the remaining elements in the array. This demonstrated in the code below.

#include <iostream>

void PrintArray(int iaArray[], int iLength) {
    using namespace std;
    for (int iIndex = 0; iIndex < iLength; ++iIndex) {
        cout << iaArray[iIndex] << "  ";
    }
    cout << endl;
}

int main() {
    using namespace std;

    int iaArray[] = {34, 17, 23, 35, 45, 9, 1};
    int iLength = 7;

    cout << "Unsorted: ";
    PrintArray(iaArray, iLength);

    // Selection sort
    for (int i = 0; i < iLength - 1; ++i) {
        int iSmallest = i;
        for (int j = i + 1; j < iLength; ++j) {
            if (iaArray[iSmallest] > iaArray[j]) {
                iSmallest = j;
            }
        }
        // Put the smallest remaining element in the ith position
        int iSwap           = iaArray[iSmallest];
        iaArray[iSmallest]  = iaArray[i];
        iaArray[i]          = iSwap;
    }

    cout << "Sorted:   ";
    PrintArray(iaArray, iLength);

    cin.get();
    return 0;
}

The C++ code for the selection sort is given above, which you can copy and paste into a simple C++ Console project to test it for yourself. The program consists of the function PrintArray(), which is used to output the array before and after we sort it. In the main function, we initialize an array, output it and then we have the selection sort code after the comment: "Selection sort." Finally, we output the sorted array.

The C++ selection sort code above begins with a for-loop that runs up through the second to last entry. This loop is used to set each index to next smallest element, and it does not need to run for the last entry for the simple reason that the last entry is already sorted once we get to it. Inside the outer for-loop, we use the int iSmallest to hold the index of the smallest of the remaining entries, where the index is i or greater. The index iSmallest is set by the inner loop every time it encounters a smaller entry. After the inner loops runs, the index iSmallest holds the index of the smallest remaining entries and the next three lines swap it into the ith position. Compiling and executing the code gives the output below.