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
- Compare
arr[j]andarr[j+1]for every adjacent pair - If
arr[j] > arr[j+1], swap them - After each full pass, the largest remaining element is in its final position
- 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>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(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]) {
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) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main(void) {
int n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements: ", n);
for (int 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);
return 0;
}
Code Explanation
- Outer loop (
i) — runs n-1 passes. After passi, the lastielements 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
| Case | Time | When it occurs |
|---|---|---|
| Best | O(n) | Array already sorted — one pass, no swaps, early exit |
| Average | O(n²) | Random input |
| Worst | O(n²) | Array sorted in reverse order |
| Space | O(1) | In-place — no extra array needed |
Bubble Sort is stable — equal elements are never swapped, so their original order is preserved.
Bubble Sort vs Other Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
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
swappedoptimisation — 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.