Selection Sort in C, C++, Java, Python and C#: Swaps, Stability and Speed

Selection sort makes exactly n(n − 1)/2 comparisons on every input, sorted or not, and at most n − 1 swaps. The comparison count is fixed, but the running time was not. The same C source sorted 20,000 integers in 469–476 ms when built with GCC and 101–112 ms when built with Clang, both at -O2. The cause was one instruction in GCC’s inner loop.

This guide traces selection sort on a small array, gives implementations in C, C++, Java, Python and C#, and measures what the algorithm does: the swap count predicted on paper and then measured, a stable variant, a double-ended variant that does not save comparisons, and the compiler difference traced to its instruction. It closes with three mistakes that still produce sorted-looking output. Every program was compiled and run for this article on Ubuntu 24.04: C with GCC 13.3 and Clang 18.1.3 (-std=c11 and -std=c17), C++ with g++ 13.3 and clang++ 18.1.3 (-std=c++17 and -std=c++20), all with -Wall -Wextra -pedantic and no warnings; Java on OpenJDK 21, Python 3.11, and C# on Mono 6.8. All five sort the same array and print the same result. The C and C++ code is in GitHub repositories whose builds run the tests on each change.

What Is Selection Sort?

Selection sort is a comparison sorting algorithm that repeatedly finds the smallest element in the unsorted part of an array and swaps it into the first unsorted position. After pass i, the first i elements are the i smallest, in their final order. It sorts in place, makes n(n − 1)/2 comparisons on every input, at most n − 1 swaps, and is not stable.

The algorithm’s one distinguishing property is its swap count. Bubble sort and insertion sort move elements once per out-of-order pair in the input, about n²/4 times on random data; selection sort makes at most n − 1 swaps whatever the input. That matters where writes are much more expensive than reads, and almost nowhere else. The idea of repeatedly selecting the minimum also underlies heap sort, which finds each minimum (or maximum) in O(log n) instead of O(n) by keeping the unsorted part in a heap.

How Selection Sort Works

1. Start at position i = 0.
2. Scan positions i + 1 to n − 1, remembering the index of the smallest value seen. Use a strict <, so the first of several equal minimums is kept.
3. Swap that minimum into position i, unless it is already there.
4. Advance i and repeat until one element is left; the last element is then the largest.

Worked Example

Sorting 29 10 14 37 13 5 41 22, as printed by the trace program in the repository:

Output:

start:                      29  10  14  37  13   5  41  22
pass 1: min 5, swap:         5  10  14  37  13  29  41  22
pass 2: min 10, no swap:     5  10  14  37  13  29  41  22
pass 3: min 13, swap:        5  10  13  37  14  29  41  22
pass 4: min 14, swap:        5  10  13  14  37  29  41  22
pass 5: min 22, swap:        5  10  13  14  22  29  41  37
pass 6: min 29, no swap:     5  10  13  14  22  29  41  37
pass 7: min 37, swap:        5  10  13  14  22  29  37  41

Seven passes make 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons, which is n(n − 1)/2 for n = 8, and they would make 28 on any 8-element input. Only five swaps were needed, because passes 2 and 6 found the minimum already in place. Pass 1 shows why the algorithm is not stable: it moves 29 from the front to index 5 in one jump, past everything in between. If one of those skipped elements had been another 29, the two would have changed order.

Selection Sort in C

The header declares the standard version and the two variants measured later:

/* selection_sort.h - selection sort and two variants for int arrays */
#ifndef SELECTION_SORT_H
#define SELECTION_SORT_H

#include <stddef.h>

void selection_sort(int a[], size_t n);
void stable_selection_sort(int a[], size_t n);
void double_selection_sort(int a[], size_t n);

#endif

Every comparison goes through SORT_LESS(x, y) and every swap through SORT_SWAP, so the counting program can measure both without a second copy of the algorithm:

/* selection_sort.c - selection sort in C11.
 * SORT_LESS(x, y) means "x sorts before y" and SORT_SWAP exchanges two
 * elements. Test programs redefine them (and SORT_ON_SHIFT) before
 * including this file, to count what the algorithms do. */
#include "selection_sort.h"

static void swap_int(int *x, int *y) { int t = *x; *x = *y; *y = t; }

#ifndef SORT_LESS
#define SORT_LESS(x, y) ((x) < (y))
#endif
#ifndef SORT_SWAP
#define SORT_SWAP(x, y) swap_int(x, y)
#endif
#ifndef SORT_ON_SHIFT
#define SORT_ON_SHIFT() ((void)0)      /* lets a test program count shifts */
#endif

/* In place, at most n - 1 swaps, n(n-1)/2 comparisons. Not stable. */
void selection_sort(int a[], size_t n)
{
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++)
            if (SORT_LESS(a[j], a[min]))
                min = j;
        if (min != i)                    /* never swap an element with itself */
            SORT_SWAP(&a[i], &a[min]);
    }
}

/* Stable variant: instead of swapping, shift a[i..min-1] one place right
 * and put the minimum at a[i]. Same comparisons, far more moves. */
void stable_selection_sort(int a[], size_t n)
{
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++)
            if (SORT_LESS(a[j], a[min]))
                min = j;
        int v = a[min];
        for (size_t k = min; k > i; k--) {
            a[k] = a[k - 1];
            SORT_ON_SHIFT();
        }
        a[i] = v;
    }
}

/* Finds the minimum and the maximum in one pass and places both.
 * Half as many passes; not fewer comparisons. */
void double_selection_sort(int a[], size_t n)
{
    if (n < 2)
        return;
    size_t lo = 0, hi = n - 1;
    while (lo < hi) {
        size_t min = lo, max = lo;
        for (size_t j = lo + 1; j <= hi; j++) {
            if (SORT_LESS(a[j], a[min]))
                min = j;
            else if (SORT_LESS(a[max], a[j]))
                max = j;
        }
        if (min != lo)
            SORT_SWAP(&a[lo], &a[min]);
        if (max == lo)                   /* the max was at lo: it just moved */
            max = min;
        if (max != hi)
            SORT_SWAP(&a[hi], &a[max]);
        lo++;
        hi--;
    }
}

A short program that calls all three:

/* selection_example.c - calls selection_sort() and its two variants */
#include <stdio.h>
#include <limits.h>
#include "selection_sort.h"

static void print_array(const char *label, const int a[], size_t n)
{
    printf("%-10s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("\n");
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int b[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int c[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int edge[] = { 0, INT_MAX, -1, INT_MIN, 0 };
    size_t n = sizeof a / sizeof a[0];

    print_array("before:", a, n);
    selection_sort(a, n);
    print_array("after:", a, n);
    stable_selection_sort(b, n);
    print_array("stable:", b, n);
    double_selection_sort(c, n);
    print_array("double:", c, n);
    selection_sort(edge, 5);
    print_array("limits:", edge, 5);
    selection_sort(NULL, 0);             /* empty: i + 1 < n is false */
    return 0;
}

Output:

before:    29 10 14 37 13 5 41 22
after:     5 10 13 14 22 29 37 41
stable:    5 10 13 14 22 29 37 41
double:    5 10 13 14 22 29 37 41
limits:    -2147483648 -1 0 0 2147483647

The details in selection_sort():

• The outer loop runs while i + 1 < n. Writing i < n - 1 with a size_t n of 0 computes SIZE_MAX and runs off the array; adding instead of subtracting avoids that, so selection_sort(NULL, 0) is safe.
• min is an index, not a value, so the swap knows where the minimum came from.
• The comparison is strict. Among equal minimums, the first one found is kept. That does not make the algorithm stable, but it avoids pointless swaps between equal values.
• The min != i check skips self-swaps. With the ordinary three-assignment swap it only saves work; with some swap implementations it is required for correctness, as the XOR mistake below shows.

Comparisons and Swaps, Measured

The counting program runs the three functions on 10,000 values in four arrangements and counts comparisons, swaps, and the element shifts made by the stable variant:

Output:

n = 10000          comparisons     swaps  stable cmp    shifts  double cmp
sorted                 49995000         0    49995000         0    50000000
reversed               49995000      5000    49995000  49995000    25000000
random                 49995000      9988    49995000  24610088    49961138
10 distinct            49995000      8997    49995000  22693856    49990512

swaps on 100 random permutations: mean 9990.40, predicted n - H(n) = 9990.21

What the table shows:

• Comparisons are the same on every input: 49,995,000, which is 10,000 × 9,999 / 2. Selection sort cannot notice that its input is already sorted.
• Swaps follow the input. Sorted input needs none. Reversed input needs exactly n/2 = 5,000: each swap puts two elements in their final places at once, the smallest and the largest remaining.
• The average swap count on random input was predicted before it was measured. A pass swaps unless the minimum of the remaining elements is already at the front. For a random permutation, the expected number of swaps works out to n − Hₙ, where Hₙ = 1 + 1/2 + … + 1/n is the n-th harmonic number. I confirmed that formula exactly by enumerating every permutation of up to 7 elements; for n = 10,000 it predicts 9,990.21. Over 100 random permutations of 10,000 elements, the measured mean was 9,990.40.

A stable selection sort

stable_selection_sort() removes the swap. It takes the minimum out, shifts the elements between i and the minimum one place right, and puts the minimum at i. Nothing jumps over an equal value, so the result is stable. The comparisons stay at 49,995,000; the moves do not. Shifting costs one move per element passed over: 24,610,088 shifts on the random input and 49,995,000 on reversed input, against at most 9,999 swaps for the unstable version. Every element passed over is strictly larger than the minimum, so each shift removes exactly one out-of-order pair, and the total equals the input’s inversion count (reasoned from the code; the reversed row, 49,995,000 = n(n − 1)/2, agrees). The stable variant ends up with insertion sort‘s moves and selection sort’s comparisons, the worse of each.

Double selection sort does not halve the work

double_selection_sort() finds the minimum and the maximum in one scan and places both, so it needs half as many passes. It does not need half as many comparisons. Each element in a scan is compared with the current minimum and, when that test fails, with the current maximum. On random input that is about 2 comparisons per element over half as many passes, and the table shows the result: 49,961,138 comparisons against 49,995,000. On sorted input every element fails the first test, so the variant made 50,000,000 comparisons, more than the ordinary version. Only reversed input, where the first test succeeds every time, got the halving: 25,000,000.

The if (max == lo) max = min; line in the double version carries its correctness. If the maximum was at lo, the first swap has just moved it to where the minimum was. Removing that line makes the repository’s correctness test fail.

How This Was Measured

No CPU pinning or frequency-scaling control was used, and all timings come from this one virtual machine. The comparison and swap counts above are exact and do not depend on it.

Why GCC’s Build Was Four Times Slower

One run of the timing program built with GCC:

Output:

ms, n = 20000, median of 5   random     sorted
selection sort                   473.2      492.7
stable selection                 139.8      155.7
double selection                 232.4      235.5
exchange sort                    437.1      276.2

Across three runs per compiler, the medians fell in these ranges (milliseconds, n = 20,000):

The GCC build of selection_sort() took about 470 ms on sorted input as well as random. That rules out branch misprediction as the cause, because on sorted input the minimum never changes and every branch is predictable. The GCC build of stable_selection_sort(), which has the same inner loop, took 140–181 ms. The difference is in the machine code. Compiled with -O2 -S, GCC’s inner loop for selection_sort() is:

.L5:
    movl (%rdi,%rdx,4), %r10d
    cmpl %r10d, (%rdi,%rax,4)
    cmovl %rax, %rdx
    addq $1, %rax
    cmpq %rax, %rsi
    jne .L5

and Clang’s is:

.LBB0_3:
    movl (%rdi,%rdx,4), %r10d
    movq %rdx, %r8
    cmpl (%rdi,%r9,4), %r10d
    jl .LBB0_5
    movq %r9, %r8
    jmp .LBB0_5

GCC turned if (a[j] < a[min]) min = j; into a conditional move, cmovl. That removes the branch, but it makes each iteration’s min depend on the previous iteration’s comparison, and the comparison depends on loading a[min], whose address is that min. Every iteration waits for the previous load and compare to finish. Clang kept a branch, jl. The processor predicts that the minimum does not change, which is almost always right (in a scan of m random values the minimum changes about ln m times), and it keeps starting the following iterations without waiting.

Two experiments test that explanation:

• Turning off GCC’s if-conversion (-fno-if-conversion -fno-if-conversion2) removed the cmov from the loop, and the same source ran in 140–149 ms on random input over three runs, down from about 470.
• Keeping the minimum’s value in a local variable (experiments/value_in_register.c) removes the load from the dependency chain. With GCC it ran in 134–142 ms on random input. With Clang, the same change made it slower: 167–182 ms, against 101–112 ms for the version that re-reads a[min].

So there is no source-level fix that helps both compilers, and neither build is “right”. The practical point is the one the bubble sort article reached for a different loop: an O(n²) inner loop runs hundreds of millions of times, so a one-instruction choice by the compiler shows up as a factor of four. Measure it with the compiler you ship.

Three Selection Sort Mistakes That Still Sort (or Nearly Do)

1. An XOR Swap Without the min != i Check

The XOR swap exchanges two values without a temporary. It fails when both pointers refer to the same element: the first line sets that element to zero.

/* xor_swap.c - selection sort with an XOR swap and no min != i check */
#include <stdio.h>
#include <stddef.h>

static void xor_swap(int *x, int *y)
{
    *x ^= *y;                            /* if x and y are the same element, */
    *y ^= *x;                            /* the first line sets it to 0      */
    *x ^= *y;
}

void selection_sort_xor(int a[], size_t n)
{
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        xor_swap(&a[i], &a[min]);        /* runs even when min == i */
    }
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    selection_sort_xor(a, 8);
    for (int i = 0; i < 8; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Output (GCC and Clang, identical):

5 0 13 14 22 0 37 41

The zeros are 10 and 29, exactly the two values whose passes found the minimum already in place: passes 2 and 6 in the worked example. AddressSanitizer and UndefinedBehaviorSanitizer both stayed silent, because nothing here is undefined: every access is in bounds and the XOR of a value with itself is well defined. The code does what it says. Use the ordinary swap, and keep the min != i check.

2. Swapping Inside the Inner Loop

A loop that swaps a[i] and a[j] whenever a[j] < a[i] also leaves the minimum at position i, and it is sometimes presented as selection sort. It is exchange sort, and the difference only shows up in the counts:

/* exchange_sort.c - swapping inside the inner loop still sorts, but it is
 * not selection sort: count the swaps on 10,000 random values. */
#include <stdio.h>
#include <stddef.h>

#define N 10000

static unsigned long long swaps;

static void swap_int(int *x, int *y) { int t = *x; *x = *y; *y = t; swaps++; }

static void exchange_sort(int a[], size_t n)       /* swap as you go */
{
    for (size_t i = 0; i + 1 < n; i++)
        for (size_t j = i + 1; j < n; j++)
            if (a[j] < a[i])
                swap_int(&a[i], &a[j]);
}

static void selection_sort(int a[], size_t n)      /* remember, swap once */
{
    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        if (min != i)
            swap_int(&a[i], &a[min]);
    }
}

int main(void)
{
    static int a[N], b[N];
    unsigned long long xs = 88172645463325252ULL;
    for (size_t i = 0; i < N; i++) {
        xs ^= xs << 13; xs ^= xs >> 7; xs ^= xs << 17;
        a[i] = b[i] = (int)(xs % 1000000);
    }
    swaps = 0; exchange_sort(a, N);
    printf("exchange sort:  %llu swaps\n", swaps);
    swaps = 0; selection_sort(b, N);
    printf("selection sort: %llu swaps\n", swaps);
    for (size_t i = 0; i < N; i++)
        if (a[i] != b[i]) { printf("results differ\n"); return 1; }
    printf("both results sorted and identical\n");
    return 0;
}

Output:

exchange sort:  25227840 swaps
selection sort: 9992 swaps
both results sorted and identical

Both sort correctly, so any test of the output passes. Exchange sort made 25,227,840 swaps where selection sort made 9,992, about 2,500 times as many, and it gives up the one property selection sort is chosen for. In the timing table it took 437–443 ms (GCC) and 516–535 ms (Clang) on random input.

3. Expecting Stability

Selection sort’s long-distance swap reorders equal keys, and it can take very little input to show it:

/* stability.c - selection sort's long-distance swap reorders equal keys */
#include <stdio.h>
#include <stddef.h>

typedef struct { int key; char tag; } Item;

int main(void)
{
    Item a[] = { {2,'a'}, {2,'b'}, {1,'c'} };
    size_t n = sizeof a / sizeof a[0];

    for (size_t i = 0; i + 1 < n; i++) {
        size_t min = i;
        for (size_t j = i + 1; j < n; j++)
            if (a[j].key < a[min].key)
                min = j;
        if (min != i) { Item t = a[i]; a[i] = a[min]; a[min] = t; }
    }
    for (size_t i = 0; i < n; i++)
        printf("%d%c ", a[i].key, a[i].tag);
    printf("\n");
    return 0;
}

Output:

1c 2b 2a

The first pass swaps 1c to the front and sends 2a to the back, past 2b. Unstable algorithms also preserve order by chance on many inputs, which makes this easy to miss: while preparing the C++ example below, two sets of test records came out in stable order before a third showed the reordering. A test that passes proves nothing about stability; only a counterexample is conclusive. When order among equal keys matters, use stable_selection_sort(), a stable algorithm, or the library’s stable sort.

Selection Sort Time and Space Complexity

Selection Sort in C++, Java, Python and C#

C++

In C++ the scan is std::min_element, which returns the first of several equal minimums, and the swap is std::iter_swap. Neither needs more than a forward iterator, so the template sorts a std::forward_list:

// selection_sort.hpp - generic selection sort for C++17
#ifndef SELECTION_SORT_HPP
#define SELECTION_SORT_HPP

#include <algorithm>
#include <functional>
#include <iterator>

// In place, at most n - 1 swaps. Not stable. Needs only forward iterators,
// so it also sorts a std::forward_list. comp(a, b) means "a goes before b".
template <class ForwardIt, class Compare = std::less<>>
void selection_sort(ForwardIt first, ForwardIt last, Compare comp = {})
{
    for (ForwardIt i = first; i != last; ++i) {
        ForwardIt min = std::min_element(i, last, comp);  // first of the smallest
        if (min != i)
            std::iter_swap(i, min);
    }
}

#endif

// selection_demo.cpp - the generic selection sort on three containers,
// and what it does to equal keys
#include <algorithm>
#include <forward_list>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
#include "selection_sort.hpp"

template <class Range>
void print(const char* label, const Range& r)
{
    std::cout << label;
    for (const auto& x : r) std::cout << ' ' << x;
    std::cout << '\n';
}

struct Employee {
    std::string name;
    int dept;
};

int main()
{
    std::vector<int> v{29, 10, 14, 37, 13, 5, 41, 22};
    selection_sort(v.begin(), v.end());
    print("ascending:   ", v);

    selection_sort(v.begin(), v.end(), std::greater<>{});
    print("descending:  ", v);

    std::forward_list<std::string> words{"pear", "fig", "apple", "kiwi", "date"};
    selection_sort(words.begin(), words.end());
    print("forward_list:", words);

    std::vector<Employee> staff{
        {"Ava", 2}, {"Ben", 2}, {"Cleo", 1}, {"Dev", 3}};
    auto expected = staff;
    auto by_dept = [](const Employee& a, const Employee& b) { return a.dept < b.dept; };
    selection_sort(staff.begin(), staff.end(), by_dept);
    std::stable_sort(expected.begin(), expected.end(), by_dept);
    std::cout << "by dept:     ";
    for (const auto& e : staff) std::cout << ' ' << e.dept << ':' << e.name;
    bool same = std::equal(staff.begin(), staff.end(), expected.begin(),
                           [](const Employee& a, const Employee& b) { return a.name == b.name; });
    std::cout << "\nmatches std::stable_sort: " << (same ? "yes" : "no") << '\n';
    return 0;
}

Output (g++ 13.3 and clang++ 18.1.3, identical):

ascending:    5 10 13 14 22 29 37 41
descending:   41 37 29 22 14 13 10 5
forward_list: apple date fig kiwi pear
by dept:      1:Cleo 2:Ben 2:Ava 3:Dev
matches std::stable_sort: no

The last line is the instability again: Ava and Ben are both in department 2, and the first swap carried Ava past Ben when it moved Cleo to the front.

Java

// SelectionSort.java - selection sort in Java 21
import java.util.Arrays;

public class SelectionSort {

    // In place, at most n - 1 swaps. Not stable.
    static void selectionSort(int[] a) {
        for (int i = 0; i + 1 < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++)
                if (a[j] < a[min])
                    min = j;
            if (min != i) {
                int t = a[i]; a[i] = a[min]; a[min] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13, 5, 41, 22};
        selectionSort(data);
        System.out.println("Sorted: " + Arrays.toString(data));
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Python

"""Selection sort in Python 3."""


def selection_sort(a):
    """Sort list a in place with at most len(a) - 1 swaps. Not stable."""
    n = len(a)
    for i in range(n - 1):
        m = min(range(i, n), key=a.__getitem__)   # index of the first minimum
        if m != i:
            a[i], a[m] = a[m], a[i]
    return a


if __name__ == "__main__":
    data = [29, 10, 14, 37, 13, 5, 41, 22]
    print("Sorted:", selection_sort(data))

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

min(range(i, n), key=a.__getitem__) returns the index of the first minimum, matching the strict < in the other versions.

C#

// SelectionSort.cs - selection sort in C#
namespace MyCPlus.Sorting;

public static class SelectionSort
{
    // In place, at most n - 1 swaps. Not stable.
    public static void Sort(int[] a)
    {
        for (int i = 0; i + 1 < a.Length; i++)
        {
            int min = i;
            for (int j = i + 1; j < a.Length; j++)
                if (a[j] < a[min])
                    min = j;
            if (min != i)
            {
                int t = a[i]; a[i] = a[min]; a[min] = t;
            }
        }
    }
}

// Program.cs - sorts the article's array with SelectionSort.Sort
using System;

namespace MyCPlus.Sorting;

public static class Program
{
    public static void Main()
    {
        int[] data = { 29, 10, 14, 37, 13, 5, 41, 22 };
        SelectionSort.Sort(data);
        Console.WriteLine("Sorted: [" + string.Join(", ", data) + "]");
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

The swap uses a temporary on purpose. The tuple form (a[i], a[min]) = (a[min], a[i]) is defined by C# as a swap, and JetBrains Rider suggests it as the preferred idiom, but under the Mono C# compiler used here (mcs 6.8.0.105) the first version of this program printed Sorted: [5, 5, 5, 5, 5, 5, 22, 22]. A two-element test case, (a[i], a[j]) = (a[j], a[i]) on { 1, 2 }, printed 2 2 instead of 2 1. Microsoft’s own compiler was not available on the test machine, so this was not checked there; if you build with Mono’s mcs, avoid the tuple swap on array elements.

When to Use Selection Sort

Key Takeaways

• Selection sort always makes n(n − 1)/2 comparisons: 49,995,000 for 10,000 elements, sorted or not.
• Its swaps are its only advantage. At most n − 1; the average on random input matched the prediction n − Hₙ to within 0.2 (9,990.40 measured, 9,990.21 predicted).
• Swapping inside the inner loop is a different algorithm. It still sorts, with about 2,500 times as many swaps.
• Guard the self-swap. An XOR swap without min != i zeroed two of eight values, and no sanitizer reported it.
• Double selection halves the passes, not the comparisons, and on sorted input it made more.
• The compiler decided the speed. One cmov in GCC’s inner loop made the same source about 4.5 times slower than Clang’s build, on sorted input as well as random.
• It is not stable, and a passing test does not show otherwise.

Frequently Asked Questions

Conclusion

Selection sort is the easiest sort to state and the least adaptive one to run: it does the same comparisons whatever it is given. Its interest now lies in what it makes measurable. Its swap count follows a formula you can check to one decimal place, its textbook variants fail to deliver what they appear to promise, and its inner loop is simple enough that a single instruction chosen by the compiler decided whether it took 100 or 470 milliseconds.

The same repeated selection of the minimum becomes efficient once the unsorted part is kept in a heap instead of a flat array, which turns each O(n) scan into an O(log n) operation. That is heap sort.

Source Code and Tests

The C code is in mycplus/c-examples/sorting/selection-sort and the C++ code in mycplus/cpp-examples/sorting/selection-sort . The Java, Python and C# versions are in mycplus/java-examples/sorting/selection-sort, mycplus/python-examples/sorting/selection-sort and mycplus/csharp-examples/sorting/selection-sort, each with its own tests and workflow.

Build and test either one with:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the builds check on each change:

• Compilation with warnings as errors: GCC and Clang with -Wall -Wextra -pedantic -Werror (C11 and C17; C++17 and C++20), and MSVC with /W4 /WX.
• Correctness against a reference: all three C functions against qsort() on 20,000 random arrays of 0 to 64 elements, including empty arrays, INT_MIN, INT_MAX and heavy duplication; the C++ template against std::sort on 5,000 inputs in std::vector and std::forward_list.
• The output on this page: the example, the trace, the count table (including the n − Hₙ line), the three pitfall programs and the C++ demo are compared with the output blocks above.
• Sanitizers: all tests run again under AddressSanitizer and UndefinedBehaviorSanitizer.

The builds do not run the timing program or the register experiment, because timings depend on the machine. A green badge means the code compiles on those toolchains and passes those tests; it does not reproduce the timings above.