C Program for Selection Sort with Example and Explanation

A C program for selection sort uses nested for loops to find the minimum element and swap it with the first unsorted element; for example, for (i = 0; i < n-1; i++) { min_idx = i; for (j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } sorts the array in ascending order.

Examples

Inputarr = {5, 2, 9, 1, 5}

OutputSorted array: 1 2 5 5 9

Inputarr = {3, 3, 3}

OutputSorted array: 3 3 3

Inputarr = {10}

OutputSorted array: 10

How to Think About It

To sort an array using selection sort, think of repeatedly finding the smallest number in the unsorted part and swapping it with the first unsorted element. This way, the sorted part grows from the front, and the unsorted part shrinks until the whole array is sorted.

Algorithm

1

Start from the first element and assume it is the minimum.

2

Compare this minimum with the rest of the elements to find the actual minimum.

3

Swap the found minimum element with the first element of the unsorted part.

4

Move the boundary of the sorted part one step forward.

5

Repeat until the entire array is sorted.

Code

c

#include <stdio.h>

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output

Sorted array: 11 12 22 25 64 

Dry Run

Let's trace the array {64, 25, 12, 22, 11} through the selection sort code.

1

First pass

Find minimum from index 0 to 4: minimum is 11 at index 4. Swap 64 and 11. Array becomes {11, 25, 12, 22, 64}.

2

Second pass

Find minimum from index 1 to 4: minimum is 12 at index 2. Swap 25 and 12. Array becomes {11, 12, 25, 22, 64}.

3

Third pass

Find minimum from index 2 to 4: minimum is 22 at index 3. Swap 25 and 22. Array becomes {11, 12, 22, 25, 64}.

4

Fourth pass

Find minimum from index 3 to 4: minimum is 25 at index 3. Swap 25 and 25 (no change). Array remains {11, 12, 22, 25, 64}.

Pass	Array State
1	11 25 12 22 64
2	11 12 25 22 64
3	11 12 22 25 64
4	11 12 22 25 64

Why This Works

Step 1: Finding the minimum

The inner loop uses if (arr[j] < arr[min_idx]) to find the smallest element in the unsorted part.

Step 2: Swapping elements

After finding the minimum, the code swaps it with the first unsorted element to grow the sorted section.

Step 3: Repeating for all elements

The outer loop moves the boundary forward until all elements are sorted.

Alternative Approaches

Bubble Sort

c

#include <stdio.h>

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

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Bubble sort repeatedly swaps adjacent elements and is simpler but usually slower than selection sort.

Insertion Sort

c

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Insertion sort builds the sorted array one element at a time and is efficient for nearly sorted data.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, resulting in O(n^2) time complexity regardless of input order.

Space Complexity

It sorts the array in place using only a few extra variables, so space complexity is O(1).

Which Approach is Fastest?

Selection sort is simple but slower than more advanced algorithms like quicksort; insertion sort can be faster on nearly sorted data.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Small arrays, simple implementation
Bubble Sort	O(n^2)	O(1)	Teaching sorting basics, simple swaps
Insertion Sort	O(n^2)	O(1)	Nearly sorted arrays, adaptive sorting