Bubble Sort in C

Analogy categoryAnalogies

1. Introduction

Bubble sort is one of the simplest sorting algorithms taught in computer science courses. It works by repeatedly stepping through the array, comparing adjacent elements, and swapping them if they are in the wrong order. After each full pass through the array, the largest unsorted element 'bubbles up' to its correct position at the end, much like a bubble rising to the surface of water. Although bubble sort is easy to understand and implement, it is inefficient for large datasets compared to algorithms like merge sort or quick sort, so it is mainly used for teaching purposes and for sorting very small or nearly-sorted arrays.

🏏

Cricket analogy: Imagine ranking five IPL batsmen by strike rate by comparing each neighboring pair in a line and swapping if out of order — after one full walk down the line, MS Dhoni's top strike rate bubbles to the end, just like bubble sort settles the largest value.

2. Syntax

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

/* Parameters:
   arr - array of integers to sort in place
   n   - number of elements in the array

   Returns nothing; the array is sorted in ascending order in place */

3. Explanation

Bubble sort uses two nested loops. The outer loop runs for n - 1 passes. The inner loop compares each pair of adjacent elements arr[j] and arr[j + 1] from the start of the array up to the unsorted boundary, and swaps them if arr[j] > arr[j + 1]. After pass 1, the largest element is guaranteed to be at the last index; after pass 2, the second largest is in place, and so on. A common optimization adds a boolean 'swapped' flag: if no swaps occur during an entire inner pass, the array is already sorted and the algorithm can exit early, improving the best-case performance to O(n) for an already-sorted array.

🏏

Cricket analogy: The outer loop is like Rohit Sharma calling for n-1 fielding drills, while the inner loop checks each pair of fielders' throwing speed one by one; a 'swapped' flag works like a coach who ends practice early if no fielder needed repositioning.

Worked trace on [5, 1, 4, 2, 8]: Pass 1 compares (5,1)->swap->[1,5,4,2,8], (5,4)->swap->[1,4,5,2,8], (5,2)->swap->[1,4,2,5,8], (5,8)->no swap. Array is [1,4,2,5,8] and 8 is now fixed at the end. Pass 2 compares (1,4)->no swap, (4,2)->swap->[1,2,4,5,8], (4,5)->no swap. Array is [1,2,4,5,8] and no swaps happen in Pass 3, so the early-exit flag stops the algorithm.

🏏

Cricket analogy: Tracing a five-batsman order [5,1,4,2,8] like Kohli(5),Rahul(1),Pant(4),Iyer(2),Rohit(8): pass 1 swaps Kohli past Rahul, Pant, and Iyer, ending [1,4,2,5,8] with Rohit's 8 fixed; pass 2 fixes Kohli's 5, then pass 3 finds no swaps and stops.

4. Example

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (swapped == 0) {
            break; /* array is already sorted, exit 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[] = {5, 1, 4, 2, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);
    printArray(arr, n);
    return 0;
}

5. Output

text

1 2 4 5 8

6. Key Takeaways

Worst-case and average-case time complexity is O(n^2), occurring on reverse-sorted or random arrays.
Best-case time complexity is O(n), achieved only with the swapped-flag optimization on an already-sorted array.
Space complexity is O(1) since bubble sort sorts in place without extra arrays.
Bubble sort is a stable sort, meaning equal elements retain their relative order.
It is rarely used in production code; merge sort or quick sort are preferred for real-world large-scale sorting.