Sorting in C: Bubble Sort, Selection Sort, and Insertion Sort

by

Sorting arranges data into a defined order (usually ascending or descending) — and as we saw in the previous post, a sorted array unlocks fast binary search. This post covers three classic, beginner-friendly sorting algorithms: bubble sort, selection sort, and insertion sort. This is Post 2 of the Unit III series — Post 1 covered linear and binary search.

Bubble Sort

Repeatedly steps through the array, comparing adjacent elements and swapping them if they’re in the wrong order — the largest unsorted value “bubbles up” to its correct position each pass.

#include <stdio.h>

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

int main() {
    int arr[] = {5, 2, 9, 1, 5};
    int n = 5;

    bubbleSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Sample Output

Sorted array: 1 2 5 5 9
Full worked example already on this blog: See Sort an Array in Ascending Order Using Bubble Sort in C for a lab-style version with user input and detailed line-by-line explanation.

Selection Sort

Repeatedly finds the minimum element from the unsorted portion and swaps it into its correct position at the front.

#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;
            }
        }

        // swap the found minimum with the first unsorted element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {29, 10, 14, 37, 14};
    int n = 5;

    selectionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Sample Output

Sorted array: 10 14 14 29 37
Bubble sort vs. selection sort: the key difference: Bubble sort swaps adjacent elements repeatedly throughout each pass (many swaps). Selection sort scans the ENTIRE unsorted portion first to find the true minimum, and swaps only ONCE per pass, directly into place. Selection sort generally performs fewer swaps overall, though both share the same O(n²) comparison count.

Insertion Sort

Builds the sorted array one element at a time — takes each new element and inserts it into its correct position among the already-sorted elements before it, similar to how you might sort playing cards in your hand.

#include <stdio.h>

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

        // shift elements greater than key one position to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;   // insert key into its correct spot
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = 5;

    insertionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

Sample Output

Sorted array: 5 6 11 12 13

Tracing Insertion Sort

Start:        [12, 11, 13, 5, 6]
i=1, key=11:  [11, 12, 13, 5, 6]   (11 shifted before 12)
i=2, key=13:  [11, 12, 13, 5, 6]   (13 already in place, no shift needed)
i=3, key=5:   [5, 11, 12, 13, 6]   (5 shifted all the way to the front)
i=4, key=6:   [5, 6, 11, 12, 13]   (6 shifted to just after 5)
Common insertion sort bug: wrong loop start: The outer loop must start at i = 1, not i = 0 — a single element (arr[0] alone) is trivially “already sorted,” so there’s nothing to compare it against yet. Starting at i = 0 would compare arr[-1], which is out of bounds.

Comparing All Three

Algorithm Core Idea Time Complexity
Bubble Sort Repeatedly swap adjacent out-of-order pairs O(n²)
Selection Sort Repeatedly select the minimum, place it directly O(n²)
Insertion Sort Insert each element into its correct position among sorted ones O(n²) worst case, close to O(n) on nearly-sorted data
Why learn all three if they’re all O(n²)?: These are taught as foundational examples before faster O(n log n) algorithms (merge sort, quick sort) because each demonstrates a genuinely different sorting STRATEGY — swapping adjacent pairs, selecting a minimum, and incremental insertion — that reappear as building blocks in more advanced algorithms and real-world scenarios (e.g. insertion sort is actually excellent for small or already-mostly-sorted datasets, and is used internally by many real sorting library implementations for small sub-arrays).

Summary

  • Bubble sort: repeatedly swaps adjacent out-of-order elements.
  • Selection sort: repeatedly finds the minimum of the unsorted portion and places it directly.
  • Insertion sort: builds a sorted section one element at a time by inserting each new element into its correct place.
  • All three are O(n²) in the worst case — simple to understand and implement, but not the fastest choice for very large datasets.

Further Reading

Next in this series: functions for Unit III — user-defined functions, inter-function communication, storage classes, and scope rules.

Leave a Comment