Selection Sort

Selection sort is a sorting algorithm. It is one of the more inefficient sorting algorithms available. It takes in the worst case $O(n^2)$ in time complexity.

How Does Selection Sort... Sort?

The idea behind selection sort is very simple. We iterate through our array and find the index of the smallest element. Once we pass through the array we swap the first value with current minimum value.

I like to think of it as a claw machine grabbing the minumum element at every iteration and placing it in $n - i^{ith}$ position.

Now the first position is sorted. We do this for the rest of the $n - i$ elements (because the first element is now sorted). That's it.

It's easy to see why this is $O(n^2)$. For every element $i$ we have to iterate through the array $n - i$ times. Let's say we have an array of $n=5$. Then we have to iterate:

Which by arithmetic progression we know to be:

In Big O analysis we can drop the constants and keep the dominant power, which in this case is $n^2$, thus having a $O(n^2)$.

Implementation

Below is an implementation.

#include <iostream>
#include <vector>
 
using namespace std;
 
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
 
vector<int> selection_sort(vector<int> &nums) {
 
    for (int i = 0; i < nums.size(); i++) {
        int idx = i;
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[j] < nums[idx]) {
                idx = j;
            }
        }
        swap(nums[i], nums[idx]);
    }
 
    return nums;
}
 
void print_vector(const vector<int> &vec) {
    for (auto num: vec) {
        cout << num << " ";
    }
    cout << endl;
}
 
int main() {
    vector<int> test = {4, 6, 2, 1, 7, 8, 10, -1, 3, 16};
 
    print_vector(test);
    selection_sort(test);
    print_vector(test);
 
    return 0;
}