Sorting

Selection Sort

Repeatedly find the index of the smallest remaining element and swap it into the next "sorted prefix" slot. Unlike bubble sort, only one swap per pass.

Algorithm

Basic Implementation

basic.cpp 
#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {5, 1, 4, 2, 8};
    int n = static_cast<int>(arr.size());
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int tmp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
    std::cout << "[";
    for (size_t i = 0; i < arr.size(); ++i) {
        if (i > 0) std::cout << ", ";
        std::cout << arr[i];
    }
    std::cout << "]" << std::endl;
    return 0;
}

The pinned input [5, 1, 4, 2, 8] sorts with two real swaps. The frames keep the running minimum and swap positions visible.

Step 1 - First scan finds 1

In the first pass, min_idx moves from 5 to 1.

First pass over [5, 1, 4, 2, 8]: 1 is the running minimum.i0i1i2i3i451428imin

Step 2 - Swap 5 and 1

The smallest value moves into the first sorted slot.

After swap: [1, 5, 4, 2, 8].i0i1i2i3i415428sorted

Step 3 - Second scan finds 2

In the unsorted suffix, 2 is smaller than 5 and becomes the next minimum.

Second pass: 2 is selected from the suffix.i0i1i2i3i415428sortedimin

Step 4 - Sorted after two swaps

Swapping 5 and 2 gives [1, 2, 4, 5, 8]; later passes find no real swap.

After the second real swap: [1, 2, 4, 5, 8].i0i1i2i3i412458sortedsorted

Complexity

  • Time: O(n^2) regardless of input order
  • Space: O(1)
  • Stable: no
  • Swap count: at most n-1

Implementation notes

  • In C++, the input is a std::vector<int> initialized as {5, 1, 4, 2, 8} and n is copied from static_cast<int>(arr.size()) for the loop bounds.
  • Both scan indexes are int: i runs while i < n - 1, and j scans from i + 1 to n - 1, keeping each arr[j] and arr[minIdx] read inside the vector.
  • int minIdx = i tracks the current minimum slot. The comparison arr[j] < arr[minIdx] mutates only that scalar index until the pass ends.
  • Swaps are manual and guarded by if (minIdx != i): int tmp = arr[i], then assignments to arr[i] and arr[minIdx]. The checked source does not call std::swap.
  • The trace shows pass i=0 swapping indexes 0 and 1, pass i=1 swapping indexes 1 and 3, then two no-swap passes with the array already [1, 2, 4, 5, 8].
  • Output is streamed with std::cout, a size_t print loop, comma separators, and std::endl. Visible allocation is the vector storage; mutation is vector element assignment plus scalar minIdx and tmp.
running minimum `minIdx` tracks the index of the smallest value seen in `arr[i..]`.
sorted prefix After each pass, `arr[0..i]` is the final sorted prefix.