Table of Contents

Selection Sort

<aside> 💡 Selection Sort is a sorting algorithm that orders a collection of items from smallest to largest by keeping track of the minimum value and moving it to the front of a list/array.

</aside>

Implementation

#include <vector>

std::vector<int> swap (std::vector<int>& list_of_nums, int i, int i_min) {
    int temp = list_of_nums.at(i);
    list_of_nums.at(i) = list_of_nums.at(i_min);
    list_of_nums.at(i_min) = temp;

    return list_of_nums;
}

std::vector<int> selectionSort (std::vector<int>& list_of_nums) {
    for (int i = 0; i < list_of_nums.size(); i++) {
        int i_min = i;
        for (int j = i + 1; j < list_of_nums.size(); j++) {
            if (list_of_nums.at(i_min) > list_of_nums.at(j))
                i_min = j;
        }
        swap(list_of_nums, i, i_min);
    }
    return list_of_nums;
}

int main() {
    std::vector<int> list_of_nums = {5, 6, 1, 3};
    selectionSort(list_of_nums);
    return 0;
}

Code Walkthrough

Time Complexity Explanation

<aside> 💡 As $n$, the size of the vector/array increases, the time it takes go through each element and swap them in the outer loop is $O(n)$ and the time it takes compare those elements in the inner loop is also $O(n)$. Thus, selection sort has a time complexity of $O(n^2)$.

</aside>