What You Will Learn

• What sorting means and why ordered data is valuable
• How the selection sort algorithm builds a sorted region one element at a time
• How to trace every pass on a six-element array
• Two ways to run a pass: remember the minimum index, or swap as you go
• How many comparisons and swaps selection sort needs
• Why selection sort is still interesting in embedded C programming

Prerequisites

• One-dimensional arrays and nested for loops
• Comparison operators and the if statement
• Binary search from the previous two lectures (it needs sorted input)

What Does Sorting Mean?

Sorting arranges the elements of an array in a defined order. Ascending order goes from the smallest value to the largest, and descending order is the reverse. Take the list 5, 11, 15, 8, 7: in ascending order it becomes 5, 7, 8, 11, 15.

Sorted data is useful for three reasons. People can read it easily, algorithms like binary search can use it, and finding minimum, maximum or median values becomes trivial. Many firmware tasks, such as ordering sensor samples before taking a median, begin with a small sort.

The Core Idea of the Selection Sort Algorithm

Imagine a row of cards on a table. You scan the whole row, pick the smallest card, and swap it with the card in the first position. The first position is now final. Then you scan the remaining cards, pick the smallest of those, and swap it into the second position. You keep going until only one card is left, and that card must already be in the right place.

In C terms, the array is divided into two regions that change on every pass:

• A sorted region at the left. Its elements are final and will never move again.
• An unsorted region at the right. The next smallest value is somewhere inside it.

For an array of N elements the algorithm needs N – 1 passes. After pass 1 one element is in place, after pass 2 two elements, and so on. The last element needs no pass because it is automatically the largest.

The Steps in Plain Words

1. Set the pass number i to 0.
2. Look at positions i to N - 1 and find where the smallest value lives.
3. Swap that smallest value with the element at position i.
4. Increase i by one. Repeat from step 2 until i reaches N - 1.

Selection Sort Algorithm: Worked Example

We will sort six values: 45, 12, 38, 7, 25, 19. Grey pills show the sorted region. Blue pills show the element that was just moved into place.

Notice what pass 2 teaches: a pass does not always swap. If the smallest remaining value is already in front, nothing moves. Four swaps were enough here for six elements.

Finding the Smallest Element: A Building Block

The heart of each pass is a loop that remembers the index of the smallest value seen so far. Here is that loop on its own, so you can run it before the full sort. Save it as ep_find_min.c.

#include <stdio.h>

#define N 6

/* Returns the index of the smallest element in a[start..n-1]. */
static int find_min_index(const int a[], int n, int start)
{
    int min = start;

    for (int j = start + 1; j < n; j++) {
        if (a[j] < a[min])
            min = j;
    }
    return min;
}

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

    for (int start = 0; start < N - 1; start++) {
        int m = find_min_index(a, N, start);

        printf("scan from index %d: smallest is %d at index %d\n",
               start, a[m], m);
    }
    return 0;
}

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

Expected output:

scan from index 0: smallest is 7 at index 3
scan from index 1: smallest is 7 at index 3
scan from index 2: smallest is 7 at index 3
scan from index 3: smallest is 7 at index 3
scan from index 4: smallest is 19 at index 5

This program never swaps, so the value 7 keeps winning until the scan starts after it. A real sort would move 7 to the front in the first pass, and the later scans would find the next smallest values instead. That is exactly the difference between scanning and sorting.

Two Ways to Run One Pass

Textbooks describe a pass in two slightly different ways. Both produce a sorted array and both are called selection sort in everyday use.

Method A: Swap Whenever You See a Smaller Value

Compare the element at position i with every element after it. Whenever the later element is smaller, exchange the two immediately. When the inner loop ends, position i holds the smallest value, but many swaps may have happened on the way.

Method A needs 2 + 2 + 3 + 2 + 1 = 10 swaps for the same array. The values in the middle of the array are shuffled around while the pass searches.

Method B: Remember the Index, Swap Once

Walk through the unsorted region, keep the index of the smallest value found, and perform a single swap at the end of the pass. This is the trace in the worked example, and it needed only 4 swaps.

Property	Method A (swap as you go)	Method B (minimum index)
Comparisons for N = 6	15	15
Swaps for our array	10	4
Maximum swaps for any array	N(N-1)/2	N – 1
Code length	Slightly shorter	One extra variable
Best when	Writes are cheap	Writes are expensive (flash, EEPROM)

How Many Comparisons Does Selection Sort Need?

Pass 1 compares N – 1 pairs, pass 2 compares N – 2 pairs, and the last pass compares 1 pair. The total is N(N – 1) / 2. The comparison count never depends on how the data was arranged: an already sorted array costs exactly as many comparisons as a reversed one.

N	Comparisons N(N-1)/2	Passes N-1
6	15	5
10	45	9
100	4,950	99
1,000	499,500	999

Growth is quadratic, written O(N²). Selection sort is therefore fine for tens or a few hundred elements, but it is the wrong tool for sorting a million samples.

Selection Sort in Embedded C Programming

• Almost no memory. It sorts in place using a handful of integer variables, with no recursion and no heap.
• Few writes. The minimum-index method performs at most N – 1 swaps. That matters when each write to flash or EEPROM costs time and wears the cell.
• Predictable timing. The comparison count is fixed, so execution time is easy to estimate.
• Small data sets. Sorting 8 or 16 sensor readings before choosing the median is a typical use.

Common Mistakes and Troubleshooting

• Running the outer loop to N instead of N – 1. It adds a useless last pass and, in method A, can read past the array.
• Swapping values without a temporary variable. Writing a[i] = a[j]; a[j] = a[i]; destroys one value. Keep a third variable.
• Storing the minimum value but not its index. You need the index to know which element to swap.
• Starting the inner loop at i instead of i + 1. It compares an element with itself and wastes work.
• Expecting stability. Selection sort can reorder equal values, which matters if you sort records by one field.

Best Practices

• Write the pass description in a comment before coding, then match the loops to it.
• Keep the inner “find minimum” loop in its own function so it can be tested alone.
• Sort a copy of the data when the original order is still needed elsewhere.
• Do a sanity check after sorting during development: every element must be less than or equal to its right neighbour.

Summary and Key Takeaways

• The selection sort algorithm grows a sorted region on the left, one element per pass.
• N elements need N – 1 passes and exactly N(N – 1) / 2 comparisons.
• Remembering the minimum index keeps swaps to at most N – 1.
• It uses constant memory and has quadratic time, so keep it for small arrays.

Conclusion

You can now trace the selection sort algorithm on paper, state how many comparisons it makes, and explain why two versions of the same pass give different swap counts. In the next lecture we write both versions in C, run them on the same array, and compare their output. Practise by choosing your own six numbers and filling in a table like the one above before you look at any code.

Frequently Asked Questions

Why is it called selection sort?

Because each pass selects the smallest remaining element and puts it in its final position.

How many passes does selection sort need?

N – 1 passes for N elements. After N – 1 elements are placed, the last one is automatically correct.

What is the time complexity of the selection sort algorithm?

O(N squared) for best, average and worst cases, because the number of comparisons does not depend on the data.

Is selection sort stable?

The usual swap-based version is not stable, because a swap can move an element past an equal one.

Is selection sort better than bubble sort?

Both are quadratic. Selection sort does fewer swaps, while bubble sort can stop early on data that is already almost sorted.

How do I sort in descending order?

Select the largest element in each pass instead of the smallest, which means flipping one comparison operator.

Can selection sort be used in firmware?

Yes, for small arrays where code size and memory matter more than speed.