Selection & Insertion Sort

Selection Sort vs Insertion Sort

Both algorithms grow a sorted prefix and use O(1) auxiliary space, but their work is different. Selection sort searches the unsorted suffix for its minimum and swaps it into the next slot. Insertion sort removes the next key conceptually, shifts larger prefix elements right, and inserts the key into the gap.

For general production sorting, prefer the standard algorithms library.

Selection Sort Algorithm and Trace

Invariant: before outer index i, the prefix [0,i) contains the smallest i values in final order. Find the minimum index in [i,n) and exchange it with position i.

Complete Selection Sort Function

void selection_sort(std::vector<int>& values) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        std::size_t minimum = i;
        for (std::size_t j = i + 1; j < values.size(); ++j) {
            if (values[j] < values[minimum]) minimum = j;
        }
        if (minimum != i) std::swap(values[i], values[minimum]);
    }
}

Checking minimum != i avoids a self-swap. Comparisons remain quadratic regardless of initial order. The distant swap can move an equal-key record past another, so this ordinary version is not stable.

Insertion Sort Algorithm and Trace

Invariant: before processing index i, prefix [0,i) is sorted and contains the original prefix values. Save the key, shift every larger predecessor one place right, and write the key into the open slot.

The scan stops as soon as the predecessor is not greater than the key. This early stopping makes insertion sort adaptive.

Complete, Safe C++ Program and Output

#include <iostream>
#include <utility>
#include <vector>

void selection_sort(std::vector<int>& values) {
    for (std::size_t i = 0; i < values.size(); ++i) {
        std::size_t minimum = i;
        for (std::size_t j = i + 1; j < values.size(); ++j)
            if (values[j] < values[minimum]) minimum = j;
        if (minimum != i) std::swap(values[i], values[minimum]);
    }
}

void insertion_sort(std::vector<int>& values) {
    for (std::size_t i = 1; i < values.size(); ++i) {
        const int key = values[i];
        std::size_t j = i;
        while (j > 0 && values[j - 1] > key) {
            values[j] = values[j - 1];
            --j;
        }
        values[j] = key;
    }
}

void print(const char* label, const std::vector<int>& values) {
    std::cout << label << ':';
    for (int value : values) std::cout << ' ' << value;
    std::cout << '\n';
}

int main() {
    std::vector<int> selection{29, 10, 14, 37, 13};
    std::vector<int> insertion = selection;
    selection_sort(selection);
    insertion_sort(insertion);
    print("Selection", selection);
    print("Insertion", insertion);
}

j > 0 is evaluated before values[j-1], preventing unsigned underflow. The two algorithms receive identical data for a fair comparison.

Complexity, Stability and Data Movement

A swap may represent several assignments, so measure the actual value type and storage medium before using “fewer swaps” as a performance conclusion.

Decision Guide

• Nearly sorted or small: insertion sort often performs well and is commonly used as a small-partition component inside advanced sorting implementations.
• Writes are unusually expensive: selection sort limits the number of swaps, though comparisons remain quadratic.
• Large general range: use std::sort.
• Stable library result: use std::stable_sort.
• Predictable Θ(n log n) study: learn merge sort.

Algorithm selection depends on size, current order, stability, memory, comparison cost and movement cost—not on one complexity cell alone.

Common Mistakes, Tests and Practice

Test empty, one item, sorted, reverse, equal, duplicates and negative values. Practice descending comparators, record stability, comparison/move counters and binary-insertion search (noting that shifts still cost linear time).

Authoritative References

• NIST DADS: selection sort
• NIST DADS: insertion sort
• NIST DADS: sort

Definitions, growth rates and stability properties were checked against these references. Compare one more quadratic method in bubble sort.