Choice Kind in C, C++, Java, Python and C#: With Code

Choice type makes precisely n(n − 1)/2 comparisons on each enter, sorted or not, and at most n − 1 swaps. The comparability rely is fastened, however the operating time was not. The identical C supply sorted 20,000 integers in 469–476 ms when constructed with GCC and 101–112 ms when constructed with Clang, each at -O2. The trigger was one instruction in GCC’s internal loop.

This information traces choice type on a small array, offers implementations in C, C++, Java, Python and C#, and measures what the algorithm does: the swap rely predicted on paper after which measured, a secure variant, a double-ended variant that doesn’t save comparisons, and the compiler distinction traced to its instruction. It closes with three errors that also produce sorted-looking output. Each program was compiled and run for this text 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 5 type the identical array and print the identical outcome. The C and C++ code is in GitHub repositories whose builds run the exams on every change.

What Is Choice Kind?

Choice type is a comparability sorting algorithm that repeatedly finds the smallest factor within the unsorted a part of an array and swaps it into the primary unsorted place. After go i, the primary i components are the i smallest, of their ultimate order. It kinds in place, makes n(n − 1)/2 comparisons on each enter, at most n − 1 swaps, and isn’t secure.

The algorithm’s one distinguishing property is its swap rely. Bubble type makes one adjoining swap, and insertion type one shift, per out-of-order pair within the enter, about n²/4 of them on random knowledge; choice type makes at most n − 1 swaps regardless of the enter. That issues the place writes are rather more costly than reads, and virtually nowhere else. The concept of repeatedly choosing the minimal additionally underlies heap type, which finds every minimal (or most) in O(log n) as a substitute of O(n) by holding the unsorted half in a heap.

How Choice Kind Works

1. Begin at place i = 0.
2. Scan positions i + 1 to n − 1, remembering the index of the smallest worth seen. Use a strict <, so the primary of a number of equal minimums is stored.
3. Swap that minimal into place i, except it’s already there.
4. Advance i and repeat till one factor is left; the final factor is then the most important.

Labored Instance

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

Output:

begin:                      29  10  14  37  13   5  41  22
go 1: min 5, swap:         5  10  14  37  13  29  41  22
go 2: min 10, no swap:     5  10  14  37  13  29  41  22
go 3: min 13, swap:        5  10  13  37  14  29  41  22
go 4: min 14, swap:        5  10  13  14  37  29  41  22
go 5: min 22, swap:        5  10  13  14  22  29  41  37
go 6: min 29, no swap:     5  10  13  14  22  29  41  37
go 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 might make 28 on any 8-element enter. Solely 5 swaps have been wanted, as a result of passes 2 and 6 discovered the minimal already in place. Go 1 reveals why the algorithm shouldn’t be secure: it strikes 29 from the entrance to index 5 in a single soar, previous the whole lot in between. If a type of skipped components had been one other 29, the 2 would have modified order.

Choice Kind in C

The header declares the usual model and the 2 variants measured later:

/* selection_sort.h - choice type and two variants for int arrays */
#ifndef SELECTION_SORT_H
#outline SELECTION_SORT_H

#embrace <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

Each comparability goes by means of SORT_LESS(x, y) and each swap by means of SORT_SWAP, so the counting program can measure each with out a second copy of the algorithm:

/* selection_sort.c - choice type in C11.
 * SORT_LESS(x, y) means "x kinds earlier than y" and SORT_SWAP exchanges two
 * components. Check applications redefine them (and SORT_ON_SHIFT) earlier than
 * together with this file, to rely what the algorithms do. */
#embrace "selection_sort.h"

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

#ifndef SORT_LESS
#outline SORT_LESS(x, y) ((x) < (y))
#endif
#ifndef SORT_SWAP
#outline SORT_SWAP(x, y) swap_int(x, y)
#endif
#ifndef SORT_ON_SHIFT
#outline SORT_ON_SHIFT() ((void)0)      /* lets a check program rely shifts */
#endif

/* In place, at most n - 1 swaps, n(n-1)/2 comparisons. Not secure. */
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)                    /* by no means swap a component with itself */
            SORT_SWAP(&a[i], &a[min]);
    }
}

/* Steady variant: as a substitute of swapping, shift a[i..min-1] one place proper
 * and put the minimal at a[i]. Identical comparisons, way more strikes. */
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 ok = min; ok > i; k--) {
            a[k] = a[k - 1];
            SORT_ON_SHIFT();
        }
        a[i] = v;
    }
}

/* Finds the minimal and the utmost in a single go and locations each.
 * Half as many passes; not fewer comparisons. */
void double_selection_sort(int a[], size_t n)
{
    if (n < 2)
        return;
    size_t lo = 0, hello = n - 1;
    whereas (lo < hello) {
        size_t min = lo, max = lo;
        for (size_t j = lo + 1; j <= hello; 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 simply moved */
            max = min;
        if (max != hello)
            SORT_SWAP(&a[hi], &a[max]);
        lo++;
        hi--;
    }
}

A brief program that calls all three:

/* selection_example.c - calls selection_sort() and its two variants */
#embrace <stdio.h>
#embrace <limits.h>
#embrace "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 fundamental(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("earlier than:", a, n);
    selection_sort(a, n);
    print_array("after:", a, n);
    stable_selection_sort(b, n);
    print_array("secure:", 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 fake */
    return 0;
}

Output:

earlier than:    29 10 14 37 13 5 41 22
after:     5 10 13 14 22 29 37 41
secure:    5 10 13 14 22 29 37 41
double:    5 10 13 14 22 29 37 41
limits:    -2147483648 -1 0 0 2147483647

The main points in selection_sort():

• The outer loop runs whereas i + 1 < n. Writing i < n - 1 with a size_t n of 0 computes SIZE_MAX and runs off the array; including as a substitute of subtracting avoids that, so selection_sort(NULL, 0) is protected.
• min is an index, not a price, so the swap is aware of the place the minimal got here from.
• The comparability is strict. Amongst equal minimums, the primary one discovered is stored. That doesn’t make the algorithm secure, but it surely avoids pointless swaps between equal values.
• The min != i verify skips self-swaps. With the abnormal three-assignment swap it solely saves work; with some swap implementations it’s required for correctness, because the XOR mistake beneath reveals.

Comparisons and Swaps, Measured

The counting program runs the three capabilities on 10,000 values in 4 preparations and counts comparisons, swaps, and the factor shifts made by the secure variant:

Output:

n = 10000          comparisons     swaps  secure 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: imply 9990.40, predicted n - H(n) = 9990.21

What the desk reveals:

• Comparisons are the identical on each enter: 49,995,000, which is 10,000 × 9,999 / 2. Choice type can not discover that its enter is already sorted. The sorting algorithms comparability reveals the identical 49,995,000 on all six of its inputs, subsequent to 6 different algorithms.
• Swaps observe the enter. Sorted enter wants none. Reversed enter wants precisely n/2 = 5,000: every swap places two components of their ultimate locations without delay, the smallest and the most important remaining.
• The typical swap rely on random enter was predicted earlier than it was measured. A go swaps except the minimal of the remaining components is already on the entrance. For a random permutation, the anticipated variety of swaps works out to n − Hₙ, the place Hₙ = 1 + 1/2 + … + 1/n is the n-th harmonic quantity. I confirmed that system precisely by enumerating each permutation of as much as 7 components; for n = 10,000 it predicts 9,990.21. Over 100 random permutations of 10,000 components, the measured imply was 9,990.40.

A secure choice type

stable_selection_sort() removes the swap. It takes the minimal out, shifts the weather between i and the minimal one place proper, and places the minimal at i. Nothing jumps over an equal worth, so the result’s secure. The comparisons keep at 49,995,000; the strikes don’t. Shifting prices one transfer per factor handed over: 24,610,088 shifts on the random enter and 49,995,000 on reversed enter, in opposition to at most 9,999 swaps for the unstable model. Each factor handed over is strictly bigger than the minimal, so every shift removes precisely one out-of-order pair, and the overall equals the enter’s inversion rely (reasoned from the code; the reversed row, 49,995,000 = n(n − 1)/2, agrees). The secure variant finally ends up with insertion type‘s strikes and choice type’s comparisons, the more serious of every.

Double choice type doesn’t halve the work

double_selection_sort() finds the minimal and the utmost in a single scan and locations each, so it wants half as many passes. It doesn’t want half as many comparisons. Every factor in a scan is in contrast with the present minimal and, when that check fails, with the present most. On random enter that’s about 2 comparisons per factor over half as many passes, and the desk reveals the outcome: 49,961,138 comparisons in opposition to 49,995,000. On sorted enter each factor fails the primary check, so the variant made 50,000,000 comparisons, greater than the abnormal model. Solely reversed enter, the place the primary check succeeds each time, bought the halving: 25,000,000.

The if (max == lo) max = min; line within the double model carries its correctness. If the utmost was at lo, the primary swap has simply moved it to the place the minimal was. Eradicating that line makes the repository’s correctness check fail.

How This Was Measured

No CPU pinning or frequency-scaling management was used, and all timings come from this one digital machine. The comparability and swap counts above are actual and don’t rely upon it.

Why GCC’s Construct Was 4 Occasions Slower

One run of the timing program constructed with GCC:

Output:

ms, n = 20000, median of 5   random     sorted
choice type                   473.2      492.7
secure choice                 139.8      155.7
double choice                 232.4      235.5
alternate type                    437.1      276.2

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

The GCC construct of selection_sort() took about 470 ms on sorted enter in addition to random. That guidelines out department misprediction because the trigger, as a result of on sorted enter the minimal by no means modifications and each department is predictable. The GCC construct of stable_selection_sort(), which has the identical internal loop, took 140–181 ms. The distinction is within the machine code. Compiled with -O2 -S, GCC’s internal 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; right into a conditional transfer, cmovl. That removes the department, but it surely makes every iteration’s min rely upon the earlier iteration’s comparability, and the comparability relies on loading a[min], whose deal with is that min. Each iteration waits for the earlier load and examine to complete. Clang stored a department, jl. The processor predicts that the minimal doesn’t change, which is sort of at all times proper (in a scan of m random values the minimal modifications about ln m instances), and it retains beginning the next iterations with out ready.

Two experiments check that rationalization:

• Turning off GCC’s if-conversion (-fno-if-conversion -fno-if-conversion2) eliminated the cmov from the loop, and the identical supply ran in 140–149 ms on random enter over three runs, down from about 470.
• Retaining the minimal’s worth in a neighborhood variable (experiments/value_in_register.c) removes the load from the dependency chain. With GCC it ran in 134–142 ms on random enter. With Clang, the identical change made it slower: 167–182 ms, in opposition to 101–112 ms for the model that re-reads a[min].

So there isn’t a source-level repair that helps each compilers, and neither construct is “proper”. The sensible level is the one the bubble type article reached for a distinct loop: an O(n²) internal loop runs tons of of tens of millions of instances, so a one-instruction selection by the compiler reveals up as an element of 4. Measure it with the compiler you ship.

Three Choice Kind Errors That Nonetheless Kind (or Almost Do)

1. An XOR Swap With out the min != i Test

The XOR swap exchanges two values with out a short-term. It fails when each pointers consult with the identical factor: the primary line units that factor to zero.

/* xor_swap.c - choice type with an XOR swap and no min != i verify */
#embrace <stdio.h>
#embrace <stddef.h>

static void xor_swap(int *x, int *y)
{
    *x ^= *y;                            /* if x and y are the identical factor, */
    *y ^= *x;                            /* the primary line units 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 fundamental(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, similar):

5 0 13 14 22 0 37 41

The zeros are 10 and 29, precisely the 2 values whose passes discovered the minimal already in place: passes 2 and 6 within the labored instance. AddressSanitizer and UndefinedBehaviorSanitizer each stayed silent, as a result of nothing right here is undefined: each entry is in bounds and the XOR of a price with itself is nicely outlined. The code does what it says. Use the abnormal swap, and preserve the min != i verify.

2. Swapping Contained in the Interior Loop

A loop that swaps a[i] and a[j] at any time when a[j] < a[i] additionally leaves the minimal at place i, and it’s generally introduced as choice type. It’s alternate type, and the distinction solely reveals up within the counts:

/* exchange_sort.c - swapping contained in the internal loop nonetheless kinds, however it's
 * not choice type: rely the swaps on 10,000 random values. */
#embrace <stdio.h>
#embrace <stddef.h>

#outline N 10000

static unsigned lengthy lengthy 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)      /* keep in mind, swap as soon as */
{
    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 fundamental(void)
{
    static int a[N], b[N];
    unsigned lengthy lengthy 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("alternate type:  %llu swapsn", swaps);
    swaps = 0; selection_sort(b, N);
    printf("choice type: %llu swapsn", swaps);
    for (size_t i = 0; i < N; i++)
        if (a[i] != b[i]) { printf("outcomes differn"); return 1; }
    printf("each outcomes sorted and identicaln");
    return 0;
}

Output:

alternate type:  25227840 swaps
choice type: 9992 swaps
each outcomes sorted and similar

Each type appropriately, so any check of the output passes. Trade type made 25,227,840 swaps the place choice type made 9,992, about 2,500 instances as many, and it offers up the one property choice type is chosen for. Within the timing desk it took 437–443 ms (GCC) and 516–535 ms (Clang) on random enter.

3. Anticipating Stability

Choice type’s long-distance swap reorders equal keys, and it may take little or no enter to indicate it:

/* stability.c - choice type's long-distance swap reorders equal keys */
#embrace <stdio.h>
#embrace <stddef.h>

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

int fundamental(void)
{
    Merchandise 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) { Merchandise t = a[i]; a[i] = a[min]; a[min] = t; }
    }
    for (size_t i = 0; i < n; i++)
        printf("%dpercentc ", a[i].key, a[i].tag);
    printf("n");
    return 0;
}

Output:

1c 2b 2a

The primary go swaps 1c to the entrance and sends 2a to the again, previous 2b. Unstable algorithms additionally protect order by probability on many inputs, which makes this simple to overlook: whereas making ready the C++ instance beneath, two units of check data got here out in secure order earlier than a 3rd confirmed the reordering. A check that passes proves nothing about stability; solely a counterexample is conclusive. When order amongst equal keys issues, use stable_selection_sort(), a secure algorithm, or the library’s secure type.

Choice Kind Time and Area Complexity

Choice Kind in C++, Java, Python and C#

C++

In C++ the scan is std::min_element, which returns the primary of a number of equal minimums, and the swap is std::iter_swap. Neither wants greater than a ahead iterator, so the template kinds a std::forward_list:

// selection_sort.hpp - generic choice type for C++17
#ifndef SELECTION_SORT_HPP
#outline SELECTION_SORT_HPP

#embrace <algorithm>
#embrace <purposeful>
#embrace <iterator>

// In place, at most n - 1 swaps. Not secure. Wants solely ahead iterators,
// so it additionally kinds a std::forward_list. comp(a, b) means "a goes earlier than b".
template <class ForwardIt, class Examine = std::much less<>>
void selection_sort(ForwardIt first, ForwardIt final, Examine comp = {})
{
    for (ForwardIt i = first; i != final; ++i) {
        ForwardIt min = std::min_element(i, final, comp);  // first of the smallest
        if (min != i)
            std::iter_swap(i, min);
    }
}

#endif

// selection_demo.cpp - the generic choice type on three containers,
// and what it does to equal keys
#embrace <algorithm>
#embrace <forward_list>
#embrace <purposeful>
#embrace <iostream>
#embrace <string>
#embrace <vector>
#embrace "selection_sort.hpp"

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

struct Worker {
    std::string identify;
    int dept;
};

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

    selection_sort(v.start(), v.finish(), std::higher<>{});
    print("descending:  ", v);

    std::forward_list<std::string> phrases{"pear", "fig", "apple", "kiwi", "date"};
    selection_sort(phrases.start(), phrases.finish());
    print("forward_list:", phrases);

    std::vector<Worker> workers{
        {"Ava", 2}, {"Ben", 2}, {"Cleo", 1}, {"Dev", 3}};
    auto anticipated = workers;
    auto by_dept = [](const Worker& a, const Worker& b) { return a.dept < b.dept; };
    selection_sort(workers.start(), workers.finish(), by_dept);
    std::stable_sort(anticipated.start(), anticipated.finish(), by_dept);
    std::cout << "by dept:     ";
    for (const auto& e : workers) std::cout << ' ' << e.dept << ':' << e.identify;
    bool identical = std::equal(workers.start(), workers.finish(), anticipated.start(),
                           [](const Worker& a, const Worker& b) { return a.identify == b.identify; });
    std::cout << "nmatches std::stable_sort: " << (identical ? "sure" : "no") << 'n';
    return 0;
}

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

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 final line is the instability once more: Ava and Ben are each in division 2, and the primary swap carried Ava previous Ben when it moved Cleo to the entrance.

Java

// SelectionSort.java - choice type in Java 21
import java.util.Arrays;

public class SelectionSort {

    // In place, at most n - 1 swaps. Not secure.
    static void selectionSort(int[] a) {
        for (int i = 0; i + 1 < a.size; i++) {
            int min = i;
            for (int j = i + 1; j < a.size; 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 fundamental(String[] args) {
        int[] knowledge = {29, 10, 14, 37, 13, 5, 41, 22};
        selectionSort(knowledge);
        System.out.println("Sorted: " + Arrays.toString(knowledge));
    }
}

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

Python

"""Choice type in Python 3."""


def selection_sort(a):
    """Kind record a in place with at most len(a) - 1 swaps. Not secure."""
    n = len(a)
    for i in vary(n - 1):
        m = min(vary(i, n), key=a.__getitem__)   # index of the primary minimal
        if m != i:
            a[i], a[m] = a[m], a[i]
    return a


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

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

min(vary(i, n), key=a.__getitem__) returns the index of the primary minimal, matching the strict < within the different variations.

C#

// SelectionSort.cs - choice type in C#
namespace MyCPlus.Sorting;

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

// Program.cs - kinds the article's array with SelectionSort.Kind
utilizing System;

namespace MyCPlus.Sorting;

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

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

The swap makes use of a brief on goal. The tuple type (a[i], a[min]) = (a[min], a[i]) is outlined by C# as a swap, and JetBrains Rider suggests it as the popular idiom, however underneath the Mono C# compiler used right here (mcs 6.8.0.105) the primary model of this program printed Sorted: [5, 5, 5, 5, 5, 5, 22, 22]. A two-element check case, (a[i], a[j]) = (a[j], a[i]) on { 1, 2 }, printed 2 2 as a substitute of 2 1. Microsoft’s personal compiler was not accessible on the check machine, so this was not checked there; in case you construct with Mono’s mcs, keep away from the tuple swap on array components.

When to Use Choice Kind

Key Takeaways

• Choice type at all times makes n(n − 1)/2 comparisons: 49,995,000 for 10,000 components, sorted or not.
• Its swaps are its solely benefit. At most n − 1; the common on random enter matched the prediction n − Hₙ to inside 0.2 (9,990.40 measured, 9,990.21 predicted).
• Swapping contained in the internal loop is a distinct algorithm. It nonetheless kinds, with about 2,500 instances as many swaps.
• Guard the self-swap. An XOR swap with out min != i zeroed two of eight values, and no sanitizer reported it.
• Double choice halves the passes, not the comparisons, and on sorted enter it made extra.
• The compiler determined the velocity. One cmov in GCC’s internal loop made the identical supply about 4.5 instances slower than Clang’s construct, on sorted enter in addition to random.
• It’s not secure, and a passing check doesn’t present in any other case.

Steadily Requested Questions

Conclusion

Choice type is the simplest type to state and the least adaptive one to run: it does the identical comparisons no matter it’s given. Its curiosity now lies in what it makes measurable. Its swap rely follows a system you possibly can verify to 1 decimal place, its textbook variants fail to ship what they seem to vow, and its internal loop is easy sufficient {that a} single instruction chosen by the compiler determined whether or not it took 100 or 470 milliseconds.

The identical repeated number of the minimal turns into environment friendly as soon as the unsorted half is stored in a heap as a substitute of a flat array, which turns every O(n) scan into an O(log n) operation. That’s heap type.

Supply Code and Assessments

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# variations are in mycplus/java-examples/sorting/selection-sort, mycplus/python-examples/sorting/selection-sort and mycplus/csharp-examples/sorting/selection-sort, every with its personal exams and workflow.

Construct and check both one with:

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

What the builds verify on every 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 in opposition to a reference: all three C capabilities in opposition to qsort() on 20,000 random arrays of 0 to 64 components, together with empty arrays, INT_MIN, INT_MAX and heavy duplication; the C++ template in opposition to std::type on 5,000 inputs in std::vector and std::forward_list.
• The output on this web page: the instance, the hint, the rely desk (together with the n − Hₙ line), the three pitfall applications and the C++ demo are in contrast with the output blocks above.
• Sanitizers: all exams run once more underneath AddressSanitizer and UndefinedBehaviorSanitizer.

The builds don’t run the timing program or the register experiment, as a result of timings rely upon the machine. A inexperienced badge means the code compiles on these toolchains and passes these exams; it doesn’t reproduce the timings above.