C Selection Sort

Selection sort is one of the simplest sorting algorithms to understand and implement. It works by repeatedly finding the smallest (or largest) remaining element in an unsorted list and moving it into its correct position, one element at a time. While it isn’t the fastest algorithm for large datasets, it’s an excellent starting point for learning how sorting algorithms think about arrays, comparisons, and swaps.

Overview / How It Works

Selection sort divides an array conceptually into two parts: a sorted portion at the front (initially empty) and an unsorted portion at the back (initially the whole array). On each pass, the algorithm scans the entire unsorted portion to find the smallest value, then swaps that value into the first position of the unsorted portion — effectively growing the sorted portion by one element.

This repeats until the unsorted portion shrinks to a single element, at which point the whole array is sorted. Because the algorithm always scans the remaining unsorted elements to find the minimum, it performs a predictable, fixed number of comparisons regardless of the input’s initial order — this is different from algorithms like bubble sort or insertion sort, which can finish early on nearly-sorted data.

In terms of memory, selection sort operates in place: it only needs a few extra integer variables (an index for the current position and an index for the minimum found so far), not a second array. Every comparison happens directly on the array elements stored in contiguous memory, and swaps are done with a temporary variable to hold one value while the exchange happens. This makes selection sort’s space complexity O(1), which is one of its few genuine strengths.

The number of swaps selection sort performs is also bounded: at most n - 1 swaps for an array of n elements, because each pass performs at most one swap. This makes it attractive in situations where writing to memory (or storage) is expensive relative to reading — for example, when sorting data on flash memory where writes wear out cells faster than reads.

Syntax

Selection sort is not a built-in C library function — you implement it yourself, typically as a function operating on an array and its length. The general shape looks like this:

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}
  • arr[] — the array to sort, passed by reference (arrays decay to pointers in C, so the function modifies the caller’s array directly).
  • n — the number of elements in the array; C arrays don’t know their own length, so you must pass it explicitly.
  • i — the outer loop index, marking the boundary between the sorted and unsorted portions.
  • minIndex — tracks the index of the smallest value found so far in the current unsorted scan.
  • j — the inner loop index, scanning from i + 1 to the end of the array to find a smaller value than arr[minIndex].
  • temp — a temporary variable used to perform the swap between arr[i] and arr[minIndex].

Examples

Example 1: Sorting a small array of integers

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int numbers[] = {29, 10, 14, 37, 13};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    printf("Before: ");
    printArray(numbers, n);

    selectionSort(numbers, n);

    printf("After:  ");
    printArray(numbers, n);

    return 0;
}

Before: 29 10 14 37 13 
After:  10 13 14 29 37

This example sorts a five-element array in ascending order. Each outer loop iteration finds the minimum of the remaining unsorted elements and swaps it into place. Notice that sizeof(numbers) / sizeof(numbers[0]) is the standard C idiom for computing an array’s element count when the array is still in scope (it won’t work on a pointer parameter, which is why n must be passed separately to functions).

Example 2: Counting swaps and comparisons

#include <stdio.h>

void selectionSortWithStats(int arr[], int n, long *comparisons, long *swaps) {
    *comparisons = 0;
    *swaps = 0;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            (*comparisons)++;
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
            (*swaps)++;
        }
    }
}

int main(void) {
    int data[] = {5, 4, 3, 2, 1};
    int n = sizeof(data) / sizeof(data[0]);
    long comparisons, swaps;

    selectionSortWithStats(data, n, &comparisons, &swaps);

    for (int i = 0; i < n; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    printf("Comparisons: %ld, Swaps: %ld\n", comparisons, swaps);

    return 0;
}

1 2 3 4 5 
Comparisons: 10, Swaps: 4

This version instruments the algorithm to reveal what’s happening internally. For n = 5, the number of comparisons is always 4 + 3 + 2 + 1 = 10, no matter how the input is ordered — this confirms that selection sort’s comparison count is O(n²) regardless of input. The swap count, however, depends on the data: here all 4 swaps happen because the array was in reverse order. Guarding the swap with if (minIndex != i) avoids a wasted no-op swap when an element is already in its correct position.

Example 3: Sorting strings by length using selection sort

#include <stdio.h>
#include <string.h>

#define MAX_WORDS 5
#define MAX_LEN 20

void selectionSortByLength(char words[][MAX_LEN], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (strlen(words[j]) < strlen(words[minIndex])) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            char temp[MAX_LEN];
            strcpy(temp, words[i]);
            strcpy(words[i], words[minIndex]);
            strcpy(words[minIndex], temp);
        }
    }
}

int main(void) {
    char words[MAX_WORDS][MAX_LEN] = {"banana", "kiwi", "apple", "fig", "pear"};

    selectionSortByLength(words, MAX_WORDS);

    for (int i = 0; i < MAX_WORDS; i++) {
        printf("%s ", words[i]);
    }
    printf("\n");

    return 0;
}

kiwi fig pear apple banana

This demonstrates that selection sort generalizes to any data type as long as you can compare two elements and swap them — here the “value” being compared is strlen(words[j]) instead of a plain integer, and swapping uses strcpy instead of a direct assignment because C strings (character arrays) can’t be assigned with =. This same pattern — a custom comparison rule plus a custom swap mechanism — is exactly how you’d adapt selection sort to sort structs by a particular field.

How It Works Step by Step

Trace through sorting {29, 10, 14, 37, 13} in ascending order:

  • Pass 1 (i = 0): Scan indices 0–4. The minimum is 10 at index 1. Swap arr[0] and arr[1] → {10, 29, 14, 37, 13}.
  • Pass 2 (i = 1): Scan indices 1–4. The minimum is 13 at index 4. Swap arr[1] and arr[4] → {10, 13, 14, 37, 29}.
  • Pass 3 (i = 2): Scan indices 2–4. The minimum is 14, already at index 2. No swap needed → {10, 13, 14, 37, 29}.
  • Pass 4 (i = 3): Scan indices 3–4. The minimum is 29 at index 4. Swap arr[3] and arr[4] → {10, 13, 14, 29, 37}.
  • The outer loop ends after n - 1 passes (index 4 doesn’t need its own pass, because after placing the first four elements correctly, the last one is automatically in place).

Each pass shrinks the unsorted region by exactly one element and grows the sorted region by one, until the whole array is sorted.

Complexity

Case Time Complexity Notes
Best case O(n²) Still scans every remaining element on every pass, even if the array is already sorted.
Average case O(n²) Roughly n²/2 comparisons.
Worst case O(n²) Same comparison count as best/average — input order doesn’t affect comparisons.
Space complexity O(1) Sorts in place using only a few extra variables.
Swaps O(n) At most n – 1 swaps total.

Because selection sort always performs the same number of comparisons regardless of input order, it does not benefit from partially-sorted data the way insertion sort or bubble sort (with an early-exit flag) can. Its one real advantage is the low, predictable number of writes/swaps, which matters when writes are costly.

Selection sort is also not stable by default: equal elements can be reordered relative to each other because the algorithm swaps a found minimum into place even when a swap moves it past an equal element earlier in the array. If stability matters, you’d need a different algorithm (like insertion sort or merge sort) or a modified selection sort that shifts elements instead of swapping.

Common Mistakes

Mistake 1: Swapping inside the inner loop instead of after it

/* Wrong: swaps on every comparison instead of once per pass */
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[i]) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

This actually still produces a sorted array in this specific case, but it performs far more swaps than necessary and obscures the algorithm’s real logic — it’s closer to a variant of bubble sort than true selection sort, and it’s easy to introduce bugs when adapting it (e.g., for descending order or custom comparators). The correct approach tracks the index of the minimum and swaps only once per outer-loop pass:

for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

Mistake 2: Off-by-one errors in loop bounds

/* Wrong: outer loop runs one time too many, and reads past the array */
for (int i = 0; i <= n; i++) {
    int minIndex = i;
    for (int j = i + 1; j <= n; j++) {
        if (arr[j] < arr[minIndex]) {   /* arr[n] is out of bounds */
            minIndex = j;
        }
    }
    /* ... */
}

Using <= instead of < causes both loops to read arr[n], which is out of bounds for an array of size n (valid indices are 0 to n - 1). This is undefined behavior in C — it might crash, corrupt memory, or silently produce wrong output. Always use i < n - 1 for the outer loop and j < n for the inner loop.

Mistake 3: Forgetting to pass the array length

/* Wrong: sizeof on a function parameter gives the pointer size, not the array size */
void selectionSort(int arr[]) {
    int n = sizeof(arr) / sizeof(arr[0]);  /* n is wrong here! */
    /* ... */
}

Inside a function, an array parameter has already decayed to a pointer, so sizeof(arr) gives the size of a pointer (commonly 8 bytes on 64-bit systems), not the size of the original array. Always compute the element count in the caller (where the array is still a true array) and pass it as a separate parameter, as shown in the syntax section above.

Best Practices

  • Always pass the array length explicitly to sorting functions — never rely on sizeof inside a function that receives an array parameter.
  • Guard swaps with if (minIndex != i) to avoid unnecessary no-op writes, especially when sorting large structs where copying is expensive.
  • Use const for helper functions (like a print function) that shouldn’t modify the array, to catch accidental mutations at compile time.
  • For sorting anything other than plain integers (structs, strings), separate the comparison logic from the swap logic clearly, as this makes it easy to adapt the algorithm to sort by different keys.
  • Remember that selection sort is O(n²) — for anything beyond small arrays or teaching purposes, prefer qsort() from <stdlib.h> or an O(n log n) algorithm like merge sort or quicksort.
  • If stability (preserving the relative order of equal elements) matters for your use case, choose a different algorithm, since selection sort does not guarantee stability.

Practice Exercises

  • Exercise 1: Modify the selectionSort function to sort the array in descending order instead of ascending order (hint: look for the maximum instead of the minimum on each pass).
  • Exercise 2: Write a function selectionSortStruct that sorts an array of a struct Student { char name[30]; int score; } by score in ascending order, printing each student’s name and score after sorting.
  • Exercise 3: Adapt the algorithm to sort only a sub-range of an array, given a start and end index, and test it by sorting just the middle three elements of a 7-element array while leaving the first and last elements untouched.

Summary

  • Selection sort repeatedly finds the minimum (or maximum) of the unsorted portion of an array and swaps it into place.
  • It sorts in place with O(1) extra space and performs at most n - 1 swaps, making writes cheap.
  • Its time complexity is O(n²) in every case (best, average, worst) because it always scans the full remaining unsorted region.
  • It is not stable by default, and it does not adapt its speed to partially-sorted input.
  • Common bugs include off-by-one loop bounds, swapping too often inside the inner loop, and misusing sizeof on a pointer parameter.
  • For real-world, large-scale sorting, prefer qsort() or an O(n log n) algorithm instead.