Selection Sort and Insertion Sort

Selection sort: pick the smallest

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {64, 25, 12, 22, 11};
    int n = v.size();
    for (int i = 0; i < n - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < n; j++)
            if (v[j] < v[smallest]) smallest = j;
        swap(v[i], v[smallest]);
    }
    for (int x : v) cout << x << ' ';
    cout << endl;
    return 0;
}

Output

11 12 22 25 64 

Insertion sort: like cards in your hand

Think of it like this: Picking up cards one at a time, you slide each new card left past bigger cards until it fits. Your hand is always sorted.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {7, 3, 5, 1};
    for (int i = 1; i < (int)v.size(); i++) {
        int card = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > card) {     // shift bigger cards right
            v[j + 1] = v[j];
            j--;
        }
        v[j + 1] = card;
        for (int x : v) cout << x << ' ';
        cout << endl;
    }
    return 0;
}

Output

3 7 5 1 
3 5 7 1 
1 3 5 7 

Remember: Insertion sort is used for real: std::sort switches to it for small pieces.