How to Implement the Selection Sort Algorithm in C++

This article will explain how to implement the selection sort algorithm in C++.

Implement the Selection Sort for the std::vector Container in C++

Among the simple sorting algorithms, you can consider the selection sort as one of the simplest to implement; although, it has the O(n²) complexity, and it makes it utterly inefficient on large vectors.

The selection sort can be specified as the following routine: At first, we find the minimum value in the vector and swap it with the first element. Then, we move the pointer to the second element and find the minimum value from the remaining sub-vector to swap with the second element. We continue the previous steps for the rest of the vector while advancing the pointer one element at a time.

An alternative explanation for the selection sort might say to divide the input vector into two partsL: the first is a sorted sub-vector and the second is the remaining sub-vector of unsorted elements (which is in original order). Since the sorted sub-vector cannot be assumed to be present in the given vector, we should choose the first element as the divisor between the sorted and unsorted sub-vectors. Thus, when we start swapping the minimum values with the elements at starting positions. The vector will be naturally divided into sorted and unsorted parts.

In the following example, we implement the selectionSort function that takes the reference to the std::vector object and conducts an in-place modification of elements. We utilized the std::min_element algorithm to find the minimum value on each iteration; this helps to better understand the algorithm for the first time.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::swap(*it, *std::min_element(it, vec.end()));
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;

Alternatively, we can rewrite the selectionSort function with the second for loop that finds the minimum value for each iteration’s remaining unsorted sub-vector. This version is suitable for the algorithm complexity analysis. Even though the selection sort algorithm has a quadratic running time, it can be surprisingly efficient on smaller vectors compared to the O(nlogn) algorithms, like merge sort or heapsort. Note that we still utilize one STL function, std::swap, which is a constant time operation in this case, and it’s useful for the code example to be concise.

#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

template <typename T>
void selectionSort(vector<T> &vec) {
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    auto min = it;

    for (auto i = it + 1; i != vec.end(); ++i) {
      if (*i < *min) min = i;
    }

    std::swap(*it, *min);
  }
}

int main() {
  vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};

  printVector(vec1);
  selectionSort(vec1);
  printVector(vec1);

  return EXIT_SUCCESS;
}

Output:

43; 5; 123; 94; 359; -23; 2; -1; 
-23; -1; 2; 5; 43; 94; 123; 359;