Selection Sort

Массив делится на отсортированный префикс (изначально пустой) и остаток. На каждом шаге ищется минимум по всему остатку (полное сканирование — O(n) на шаг вне зависимости от порядка входа) и меняется местами с первым элементом остатка, после чего префикс расширяется. В отличие от insertion sort, вставки внутрь префикса не происходит — минимум просто дописывается в конец, поэтому число обменов ограничено n−1, но число сравнений всегда Θ(n²), независимо от входных данных.The array splits into a sorted prefix (initially empty) and a remainder. Each step finds the minimum across the whole remainder (a full scan — O(n) per step regardless of input order) and swaps it with the remainder's first element, after which the prefix grows. Unlike insertion sort, there's no insertion into the prefix — the minimum is simply appended, so the number of swaps is bounded by n−1, but the number of comparisons is always Θ(n²), regardless of the input.

void selection_sort(std::vector<int>& a) {
    for (size_t i = 0; i < a.size(); ++i) {
        size_t min_idx = i;
        for (size_t j = i + 1; j < a.size(); ++j) // полное сканирование остатка// full scan of the remainder
            if (a[j] < a[min_idx]) min_idx = j;
        std::swap(a[i], a[min_idx]); // ровно один обмен на шаг// exactly one swap per step
    }
}

Жёлтая заливка — текущий кандидат на минимум остатка (min_idx). Красная рамка — элемент, с которым он сравнивается прямо сейчас (j). Один обмен происходит только в конце каждого полного скана остатка.Yellow fill is the current candidate for the remainder's minimum (min_idx). The red outline is the element it's being compared against right now (j). One swap happens only at the end of each full scan of the remainder.

Всегда Θ(n²) сравнений и Θ(n) обменов — полная противоположность insertion sort, где число сравнений может быть O(n) (адаптивность), но каждая "вставка" физически двигает несколько элементов. Это делает selection sort уместным именно тогда, когда обмен дорог, а сравнение дёшево — например, когда сортируемые "элементы" — это тяжёлые объекты, а не числа, и обмен указателей на них дешевле, чем множественные операции присваивания insertion sort.Always Θ(n²) comparisons and Θ(n) swaps — the exact opposite of insertion sort, where comparisons can drop to O(n) (adaptivity) but each "insertion" physically moves several elements. This makes selection sort appropriate exactly when swaps are expensive and comparisons are cheap — e.g. when the sorted "elements" are heavy objects rather than numbers, and swapping pointers to them is cheaper than insertion sort's multiple assignment operations.