C Program to Sort an Array Using Bubble Sort — With Optimisation and Complexity

Bubble Sort is the simplest sorting algorithm to understand and implement. It works by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. After each pass, the largest unsorted element has “bubbled up” to its correct position at the end — just like air bubbles rising to the surface of water.

Bubble Sort is rarely used in production due to its O(n²) average performance, but it is an essential algorithm to know: it introduces the core idea of comparison-and-swap sorting, and its optimised version runs in O(n) on already-sorted input.

Algorithm — How It Works

1. Compare arr[j] and arr[j+1] for every adjacent pair
2. If arr[j] > arr[j+1], swap them
3. After each full pass, the largest remaining element is in its final position
4. Optimisation: if a full pass makes no swaps, the array is already sorted — stop early

Step-by-Step Example

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

Pass 1:  64>34 swap → 34>25 swap → 25>12 swap → 25>22 swap
         [34, 25, 12, 22, 64]    64 is in final position ✓

Pass 2:  34>25 swap → 34>12 swap → 34>22 swap
         [25, 12, 22, 34, 64]    34 is in final position ✓

Pass 3:  25>12 swap → 25>22 swap
         [12, 22, 25, 34, 64]    25 is in final position ✓

Pass 4:  12<22 → no swap  (swapped flag stays 0 → early exit)

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

C Program — Bubble Sort

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

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

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

        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }

        if (!swapped)   /* no swaps this pass — array is sorted */
            break;
    }
}

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);

    bubble_sort(arr, n);

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

    free(arr);
    return 0;
}

How to Compile and Run

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

Code Explanation

• Outer loop (i) — runs n-1 passes. After pass i, the last i elements are already in their final positions, so the inner loop shrinks by one each time (j < n - 1 - i).
• Inner loop (j) — scans adjacent pairs and swaps when out of order. Each iteration guarantees the current largest element reaches its correct position.
• swapped flag — the key optimisation. If the inner loop completes without a single swap, the array is already sorted and the outer loop exits immediately. This gives O(n) best case on sorted input.

Sample Output

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

Time and Space Complexity

Bubble Sort is stable — equal elements are never swapped, so their original order is preserved.

Bubble Sort vs Other Sorting Algorithms

Among O(n²) algorithms, Insertion Sort is generally preferred over Bubble Sort in practice — it performs fewer writes and adapts better to partially sorted data. Use Bubble Sort when simplicity of explanation matters, not performance.

When to Use Bubble Sort

• Teaching and learning — the simplest algorithm to visualise and explain
• Very small arrays (n < 10) where O(n²) doesn't matter
• Nearly-sorted data with the swapped optimisation — it exits in O(n)
• Anywhere you need a stable, in-place sort and code simplicity matters more than speed

Related Sorting Programs in C

• Insertion Sort in C — same complexity, fewer writes, better in practice
• Selection Sort in C
• Quick Sort in C — O(n log n) average, the practical choice
• 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.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.