What You Will Learn

• How to write a selection sort program in C using functions and a swap counter
• How the temporary variable makes a safe swap
• How to print the array after every pass to debug a sort
• Why the minimum-index method needs fewer swaps than swapping as you go
• How to change the program to sort in descending order
• How embedded code uses a tiny sort to compute a median of ADC samples

Prerequisites

• The previous lecture on the selection sort algorithm and its passes
• Functions that modify an array passed from main
• Nested for loops and the printf format specifiers %d, %3d and %-14s
• gcc or any C compiler that supports C99 or later

How a Safe Swap Works

Every sorting program needs to exchange two array elements. You cannot do it with two assignments alone, because the first assignment overwrites a value you still need. The classic fix is a temporary variable. The table follows pass 1 of our example, where a[0] holds 45 and the smallest element 7 sits at index 3.

After step 3 the two values have traded places and nothing was lost. The same three lines appear in both versions of the sort.

Complete Selection Sort Program in C

The program sorts the same array with both methods and reports the number of swaps. Save it as ep_selsort.c.

#include <stdio.h>

#define N 6

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

/* Variant A: swap whenever a[i] > a[j]. Returns number of swaps. */
static int sort_swap_as_you_go(int a[], int n)
{
    int swaps = 0;

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                swaps++;
            }
        }
    }
    return swaps;
}

/* Variant B: remember the smallest index, swap once per pass. */
static int sort_min_index(int a[], int n, int show)
{
    int swaps = 0;

    for (int i = 0; i < n - 1; i++) {
        int min = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min])
                min = j;
        }
        if (min != i) {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
            swaps++;
        }
        if (show) {
            char label[24];
            snprintf(label, sizeof label, "after pass %d:", i + 1);
            print_array(label, a, n);
        }
    }
    return swaps;
}

int main(void)
{
    int a[N] = {45, 12, 38, 7, 25, 19};
    int b[N] = {45, 12, 38, 7, 25, 19};
    int s;

    print_array("original:", a, N);
    printf("\nVariant B (min index)\n");
    s = sort_min_index(a, N, 1);
    printf("swaps = %d\n", s);

    printf("\nVariant A (swap as you go)\n");
    s = sort_swap_as_you_go(b, N);
    print_array("sorted:", b, N);
    printf("swaps = %d\n", s);
    return 0;
}

gcc -std=c17 -Wall -Wextra -o ep_selsort ep_selsort.c
./ep_selsort

Expected output:

original:      45 12 38  7 25 19

Variant B (min index)
after pass 1:   7 12 38 45 25 19
after pass 2:   7 12 38 45 25 19
after pass 3:   7 12 19 45 25 38
after pass 4:   7 12 19 25 45 38
after pass 5:   7 12 19 25 38 45
swaps = 4

Variant A (swap as you go)
sorted:         7 12 19 25 38 45
swaps = 10

Understanding the Selection Sort Program

The Outer Loop Controls the Passes

The outer loop runs i from 0 to n - 2, which gives n - 1 passes. At the start of pass i, everything to the left of index i is already final. The last element is never used as i because it falls into place by itself.

The Inner Loop Searches the Unsorted Region

The inner loop starts at i + 1 and walks to the end. In variant B it only updates the variable min. In variant A it swaps on the spot. Both loops perform 15 comparisons for six elements, exactly N(N – 1) / 2.

Why Pass 2 Printed the Same Line

In pass 2 the smallest remaining value, 12, is already at index 1, so min == i and the if (min != i) check skips the swap. That check is a small but valuable optimisation: an unneeded swap is a wasted memory write.

Comparing the Two Methods

Measure	Variant A	Variant B
Comparisons	15	15
Swaps (this array)	10	4
Prints each pass	No	Yes (show flag)
Final array	7 12 19 25 38 45 (identical)

Both sorts give the same final array, so the difference is only in the work done. On a desktop PC four extra swaps are invisible. On a device that stores data in flash, each avoided write is a real saving.

Sorting in Descending Order

Only one operator needs to change. In variant B, replace a[j] < a[min] with a[j] > a[min] and read min as “index of the largest value”. Rename the variable to best if you want the code to stay honest. In variant A, change a[i] > a[j] to a[i] < a[j]. The rest of the program stays the same.

Selection Sort in Embedded C: Median of ADC Samples

A single ADC reading can contain a spike caused by electrical noise. A median filter takes several samples, sorts them, and uses the middle one, which ignores the spike completely. The sort is tiny, so selection sort fits well. Save this as ep_median.c.

#include <stdio.h>
#include <stdint.h>

#define SAMPLES 5

static void sort_u16(uint16_t a[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min = i;

        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min])
                min = j;
        }
        if (min != i) {
            uint16_t tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}

int main(void)
{
    uint16_t s[SAMPLES] = {2051, 2047, 3999, 2049, 2050};

    printf("raw samples   :");
    for (int i = 0; i < SAMPLES; i++)
        printf(" %u", (unsigned)s[i]);
    printf("\n");

    sort_u16(s, SAMPLES);

    printf("sorted samples:");
    for (int i = 0; i < SAMPLES; i++)
        printf(" %u", (unsigned)s[i]);
    printf("\nmedian        : %u\n", (unsigned)s[SAMPLES / 2]);
    return 0;
}

gcc -std=c17 -Wall -Wextra -o ep_median ep_median.c
./ep_median

Expected output:

raw samples   : 2051 2047 3999 2049 2050
sorted samples: 2047 2049 2050 2051 3999
median        : 2050

A plain average of the five samples would be 2439, which is far from the true signal near 2050. The median stays at 2050.

Common Mistakes and Troubleshooting

Symptom	Likely cause	Fix
Array partly sorted	Outer loop stops too early	Run i while i < n - 1
One value duplicated, one missing	Swap done without tmp	Use the three-line swap
Garbage numbers at the end	Inner loop uses j <= n	Use j < n
Wrong result after the sort	Stored a[min] value instead of index	Store the index in min
Warning about format %u	Passing uint16_t directly	Cast to unsigned

Best Practices and Performance Notes

• Keep the sort in a function that takes the array and its length. Never hard-code the size inside the sorting function.
• Return the swap count while learning, then remove it in production if it is not needed.
• Selection sort is O(N squared). Beyond a few hundred elements, switch to a library sort or a faster algorithm.
• For embedded safety, use fixed-width types such as uint16_t and make sure the length is never larger than the real array.
• If the data comes from an interrupt, copy it to a local array first so the sort does not race with new samples.

Summary and Key Takeaways

• A selection sort program uses two nested loops and a safe swap with a temporary variable.
• The minimum-index version swapped 4 times where the swap-as-you-go version swapped 10 times on the same data.
• Printing the array after each pass is the fastest way to debug a sorting loop.
• A tiny sort makes a robust median filter for noisy sensor data.

Conclusion

You wrote, compiled and understood a complete selection sort program in C, and you saw it solve a real firmware problem. Combine it with the binary search from the first lectures of this chapter and you have a complete sort-then-search workflow. The next lecture introduces bubble sort, another classic method that works by comparing neighbours, and ends this batch with a quiz and interview questions.

Frequently Asked Questions

How do I write a selection sort program in C?

Use an outer loop for the passes, an inner loop to find the index of the smallest remaining element, and a temporary-variable swap at the end of each pass.

Why does the second pass not change the array in the example?

The smallest remaining value, 12, was already in the right position, so no swap was needed.

Which variant should I use in real projects?

The minimum-index version, because it performs at most N – 1 swaps and writes memory less often.

Can selection sort handle duplicate values?

Yes. Equal values stay in the array, but their relative order can change, so the sort is not stable.

How do I sort an array of uint16_t values?

Change the element type of the array and the temporary variable. The logic does not change.

Is there a built-in sort in C?

On hosted systems qsort() in the standard library sorts arrays, but many bare-metal toolchains omit it, so a small hand-written sort is common.