Sorting Algorithms in C

Analogy categoryAnalogies

1. Introduction

Sorting is the process of arranging elements of an array (or other collection) into a specific order, typically ascending or descending, based on a comparison rule. Sorted data enables faster searching (via binary search), easier duplicate detection, and cleaner data presentation. C does not sort arrays automatically — you either implement a sorting algorithm yourself or use the standard library's qsort() function.

🏏

Cricket analogy: Sorting a batting order by average is like ranking players before a draft so selectors can quickly scan for the best pick, similar to how binary search finds a name fast; C won't rank the squad for you — you write the logic yourself or call qsort(), like hiring a scout.

This lesson focuses on bubble sort, one of the simplest comparison-based sorting algorithms, and briefly surveys selection sort and insertion sort as alternatives with similar time complexity but different mechanics. All three are simple 'quadratic' sorts, suitable for learning core sorting concepts and for small datasets, but not for large-scale production sorting.

🏏

Cricket analogy: This lesson drills bubble sort the way a coach drills a basic forward defense, while briefly showing selection and insertion sort as alternative techniques — all fine for club-level cricket but not the technique an international team like India would rely on for a World Cup final.

2. Syntax

void bubbleSort(int arr[], int n);
void selectionSort(int arr[], int n);
void insertionSort(int arr[], int n);

Each function conventionally sorts the array 'arr' of size 'n' in place (modifying the original array directly through the array parameter, which decays to a pointer) and returns nothing (void), since the sorting happens by mutating the array's contents.

🏏

Cricket analogy: A fielding coach rearranging players directly on the actual practice pitch, rather than on a separate diagram, mutates the real formation in place; the coach reports nothing back verbally (void) since the rearranged team itself is the visible result, accessed through the field they're standing on.

3. Explanation

Bubble sort repeatedly steps through the array, comparing each pair of adjacent elements and swapping them if they are in the wrong order. After each full pass, the largest unsorted element 'bubbles up' to its correct position at the end of the array, so each subsequent pass needs to check one fewer element. This continues until a full pass makes no swaps, meaning the array is sorted.

🏏

Cricket analogy: Bubble sort is like a selector repeatedly comparing adjacent names on a squad list and swapping them if out of order, so the strongest player "bubbles up" to the top each pass; the process stops once a full pass swaps nobody, meaning the list is finally settled.

Selection sort works differently: on each pass, it finds the minimum element in the remaining unsorted portion of the array and swaps it into the current position, growing the sorted portion from the front. Insertion sort builds the sorted array one element at a time by taking each new element and inserting it into its correct position among the already-sorted elements to its left, similar to how one sorts playing cards in hand. All three run in O(n^2) time in the worst case, but insertion sort performs well on nearly-sorted data (close to O(n)).

🏏

Cricket analogy: Selection sort is like a selector scanning the entire remaining pool each round to pick the single best uncapped player and slot them next; insertion sort is like arranging cards in hand, sliding each new player into their correct spot among an already-ranked shortlist — both take longer on a shuffled squad but insertion is quick if the squad's already nearly ranked.

A common bubble sort bug is forgetting the 'swapped' optimization flag, which causes the algorithm to always run the full n-1 passes even if the array becomes sorted early, wasting time. Another common bug is an off-by-one error in the inner loop bound (it should run to n - i - 1, not n - i, to avoid comparing past the sorted tail or reading out of bounds).

Time complexity: bubble sort, selection sort, and insertion sort are all O(n^2) in the average and worst case. Bubble sort's best case (already sorted, with the swapped-flag optimization) is O(n). For large datasets, faster O(n log n) algorithms like merge sort and quick sort (covered in their own dedicated topics) are strongly preferred.

4. Example

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        if (!swapped) {
            break; /* array is already sorted, stop early */
        }
    }
}

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

int main(void) {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    bubbleSort(arr, n);

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

    return 0;
}

5. Output

text

Before sorting: 64 25 12 22 11 
After sorting:  11 12 22 25 64

6. Key Takeaways

Bubble sort repeatedly swaps adjacent out-of-order elements until the array is sorted.
The 'swapped' flag lets bubble sort exit early on already-sorted or nearly-sorted input, improving best-case performance to O(n).
Selection sort picks the minimum remaining element each pass; insertion sort inserts each element into its correct sorted position.
Bubble, selection, and insertion sort are all O(n^2) in the average/worst case, suitable mainly for small arrays or teaching purposes.
Dedicated Merge Sort and Quick Sort topics cover the faster O(n log n) algorithms used in production code.