Selection Sort in C — Program, Algorithm, and Complexity

Selection Sort works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. After each pass, the sorted portion grows by one element from the left.

It always performs exactly O(n²) comparisons regardless of input order — unlike Bubble or Insertion Sort, there is no early exit. Its one real advantage: it makes at most O(n) swaps, which matters when write operations are expensive (e.g. flash memory or EEPROM).

Algorithm

For position i from 0 to n-2:
Find the index of the minimum element in arr[i..n-1]
Swap it with arr[i]
After this pass, arr[0..i] is sorted

Step-by-Step Example

Sort [64, 25, 12, 22, 11]:

Pass 0:  find min in [64,25,12,22,11] → 11 at index 4 → swap with index 0
         [11, 25, 12, 22, 64]    11 in final position ✓

Pass 1:  find min in [25,12,22,64] → 12 at index 2 → swap with index 1
         [11, 12, 25, 22, 64]    12 in final position ✓

Pass 2:  find min in [25,22,64] → 22 at index 3 → swap with index 2
         [11, 12, 22, 25, 64]    22 in final position ✓

Pass 3:  find min in [25,64] → 25 at index 3 (already in place, no swap)
         [11, 12, 22, 25, 64]    25 in final position ✓

Final:   [11, 12, 22, 25, 64] ✓

C Program — Selection Sort

#include <stdio.h>
#include <stdlib.h>

void selection_sort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;

        /* Find index of minimum in arr[i+1..n-1] */
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }

        /* Swap only if minimum is not already in place */
        if (min_idx != i) {
            temp           = arr[min_idx];
            arr[min_idx]   = arr[i];
            arr[i]         = temp;
        }
    }
}

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

int main(void) {
    int n, i;
    int *arr;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    arr = (int *)malloc(n * sizeof(int));
    if (!arr) { fprintf(stderr, "malloc failed\n"); return 1; }

    printf("Enter %d elements: ", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Before sorting: ");
    print_array(arr, n);

    selection_sort(arr, n);

    printf("After sorting:  ");
    print_array(arr, n);

    free(arr);
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o selectsort selectsort.c
./selectsort

Code Explanation

Outer loop (i) — marks the boundary between the sorted (left) and unsorted (right) portions. Each iteration places one more element into its final position.
Inner loop (j) — scans the unsorted portion to find the index of the smallest element. Tracks only the index, not the value, so the swap can be done directly.
if (min_idx != i) — skips the swap when the minimum is already at position i. This avoids a redundant write and keeps the swap count minimal.

Sample Output

Enter number of elements: 6
Enter 6 elements: 64 25 12 22 11 90
Before sorting: 64 25 12 22 11 90
After sorting:  11 12 22 25 64 90

Time and Space Complexity

Case	Time	Note
Best	O(n²)	No early exit — always scans the full unsorted portion
Average	O(n²)	n(n-1)/2 comparisons always
Worst	O(n²)	Same as best — input order makes no difference
Space	O(1)	In-place, one temp variable
Swaps	O(n)	At most n-1 swaps — key advantage

Selection Sort is not stable — the swap can move an element past another equal element, changing their relative order.

Selection Sort vs Other O(n²) Algorithms

Algorithm	Comparisons	Swaps	Best case	Stable
Selection Sort	O(n²) always	O(n)	O(n²)	No
Bubble Sort	O(n²)	O(n²)	O(n) ✓	Yes
Insertion Sort	O(n²)	O(n²) shifts	O(n) ✓	Yes

When to choose Selection Sort: when the cost of writing/swapping is high relative to the cost of reading/comparing. For most in-memory sorting, Insertion Sort is a better choice because it adapts to partially sorted data.

Related Sorting Programs in C

Insertion Sort in C — adaptive, O(n) on sorted input, generally preferred over Selection Sort
Bubble Sort in C — also O(n²), stable, O(n) best case
Quick Sort in C — O(n log n) average, the practical choice for large arrays
Merge Sort in C — stable O(n log n)
Heap Sort in C — O(n log n) guaranteed, O(1) space

As an Amazon Associate we earn from qualifying purchases.

C Program to Sort N Elements Using Selection Sort — With Step-by-Step Example