Selection Sort

Intuition

This works as follow, you pick the smallest element and put it in first, and then you pick the smallest form the remaining elements and put it in the second, and so on.

#include <bits/stdc++.h>
using namespace std;

void selection_sort(vector<int> &a) {
    for (int i = 0; i < a.size(); i++) {
        int mini = i;
        for (int j = i + 1; j < a.size(); j++) {
            if (a[j] < a[mini]) mini = j;
        }
        int temp = a[mini];
        a[mini] = a[i];
        a[i] = temp;
    }
}

int main() {
    vector<int> a = {1, 4, 2, 5, 5, 6, 3, 3, 4};
    selection_sort(a);
    for (auto i : a) cout << i << " ";
    return 0;
}

Analysis

• Time complexity
  • Best: \(O(n)\), if the array is sorted
  • Average: \(O(n^2)\)
  • Worst: \(O(n^2)\)
• Space complexity - \(O(1)\)