The Selection Sort Algorithm

Bubble sort swaps neighbors on every pass, and insertion sort shifts elements to make room for each new value. Selection sort takes the most direct approach of the three: for each position, find the smallest remaining value anywhere in the list, and swap it straight into place.

The idea

Like insertion sort, selection sort keeps a sorted prefix at the front of the list. But instead of inserting each new element where it belongs among its neighbors, it scans the entire unsorted remainder to find the overall minimum, then places that minimum directly at the end of the sorted prefix with a single swap.

That makes the two halves of the work asymmetric compared to the other two algorithms: finding the minimum takes a full scan of whatever is left, but placing it costs exactly one swap — never more, regardless of how far out of place it was.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int i = 0;
int j = 1;
int minIdx = 0;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (j <= N - 1) {
            if (values[j] < values[minIdx]) {
                minIdx = j;
            }
            j++;
        } else {
            if (minIdx != i) {
                int tmp = values[i];
                values[i] = values[minIdx];
                values[minIdx] = tmp;
            }
            i++;
            if (i >= N - 1) {
                done = true;
            } else {
                minIdx = i;
                j = i + 1;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (!done && idx == minIdx) {
            PlotColor(220, 60, 60);   // smallest value found so far this pass
        } else if (idx < i) {
            PlotColor(70, 170, 90);   // sorted prefix
        } else {
            PlotColor(30, 100, 200);  // not yet reached
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

i marks the end of the sorted prefix, same as in the insertion sort sample. j scans forward through the unsorted remainder looking for a smaller value than the current minIdx; once j runs off the end, the value at minIdx gets swapped into position i and the next pass begins. As before, frame() performs one such step every few calls, and only the running minimum is highlighted — the scan pointer j moves through the blue region without its own color, since the minimum candidate is the only state that matters for where the next swap will land.

• green — the sorted prefix, values already in their final position
• red — the smallest value found so far in the current pass
• blue — not yet scanned this pass

Walking through an example

For [5, 1, 4, 2, 8], the first pass scans the whole list for the minimum:

The scan ends with minIdx = 1, so values[0] and values[1] are swapped: [1, 5, 4, 2, 8]. The next pass scans only [5, 4, 2, 8] for its minimum (2), swaps it to index 1, and so on — each pass shrinking the unsorted remainder by one and costing exactly one swap.

Why the swap count matters

Selection sort is O(n²) overall, no better than bubble or insertion sort — the scan for the minimum still costs O(n) per pass, n passes deep. What sets it apart is that it performs at most n - 1 swaps total, one per pass, regardless of how scrambled the input is. Bubble sort and insertion sort can each perform up to O(n²) swaps or shifts on a badly ordered list.

That property used to matter more than it does today: on hardware where a swap is much more expensive than a comparison — writing to slow memory, or flash storage with a limited number of write cycles — selection sort's bounded write count is a real advantage even at the same O(n²) comparison cost. It is also, unlike the other two, not stable: swapping a distant minimum into place can move it past equal elements, changing their relative order.

Conclusion

All three simple sorts do O(n²) work, but they spend it differently: bubble sort repeatedly re-scans and swaps neighbors, insertion sort shifts elements to open a gap, and selection sort scans once per pass and commits to a single swap. Comparing the three side by side is a good way to see that "same asymptotic complexity" does not mean "same algorithm" — the constants, the access pattern, and properties like stability all still depend on which one you pick.