Bubble Sort — The Swapping Dance

Real-world analogy

What is it?

Bubble sort is the simplest sorting algorithm. It works by repeatedly stepping through the array, comparing each pair of adjacent elements, and swapping them if they are in the wrong order. The largest elements gradually 'bubble up' to the end of the array, just like air bubbles rising to the surface of water.

Real-world relevance

While bubble sort is too slow for large datasets, the concept of comparing neighbors and swapping is used everywhere. Card players naturally use a form of bubble sort when arranging their hand. Teachers sometimes line up students by height using the 'compare two neighbors' approach. Understanding simple algorithms helps you appreciate why faster algorithms exist.

Key points

• What is Sorting? — Sorting means arranging elements in a specific order — usually smallest to largest (ascending) or largest to smallest (descending). Sorting is one of the most fundamental operations in computer science.
• How Bubble Sort Works — Bubble sort repeatedly walks through the array, comparing adjacent (neighboring) elements. If they are in the wrong order, it swaps them. After each full pass, the largest unsorted element 'bubbles' to its correct position at the end.
• Step-by-Step Example — Array: [5, 3, 8, 1]. Pass 1: compare 5,3 -> swap -> [3,5,8,1]; compare 5,8 -> ok; compare 8,1 -> swap -> [3,5,1,8]. Now 8 is in place! Pass 2: [3,5,1,8] -> [3,1,5,8]. Pass 3: [1,3,5,8]. Done!
• The Swap Operation — To swap two variables in C++, we use a temporary variable: int temp = a; a = b; b = temp; Or we can use the built-in swap(a, b) function which does the same thing. Swapping is the heart of bubble sort.
• How Many Passes? — For an array of n elements, we need at most n-1 passes. In each pass, we compare adjacent elements and swap if needed. After pass k, the k-th largest element is in its final position.
• Time Complexity Hint — Bubble sort compares every pair in each pass, and does up to n-1 passes. That means roughly n * n comparisons in the worst case. We write this as O(n^2). For 1000 elements, that is about 1 million comparisons — slow for big data, but fine for learning!
• Optimization: Early Stop — If we go through a complete pass without making any swaps, the array is already sorted! We can add a boolean flag to check this and stop early. This makes bubble sort faster when the data is nearly sorted.
• When to Use Bubble Sort — In competitive programming, you almost never use bubble sort for actual sorting (C++ sort() is much faster). But understanding bubble sort teaches you about comparisons, swaps, and algorithm analysis. Some CP problems specifically ask about bubble sort or count swaps.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Bubble Sort
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // Array is already sorted!
    }

    // Print sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. vector arr(n); — we create a vector (dynamic array) of size n to hold our numbers. Vectors are super handy in C++ because they manage memory for us.
2. 2. for (int i = 0; i < n - 1; i++) — the outer loop runs n-1 times. Each pass places one more element in its final position. After n-1 passes, everything is sorted.
3. 3. bool swapped = false; — this flag tracks whether we made any swaps in this pass. If we complete a pass with no swaps, the array is already sorted and we can stop early.
4. 4. for (int j = 0; j < n - 1 - i; j++) — the inner loop compares adjacent elements. We use n-1-i because after i passes, the last i elements are already in their correct positions, so we do not need to check them again.
5. 5. if (arr[j] > arr[j + 1]) — we compare two neighbors. If the left one is bigger than the right one, they are in the wrong order for ascending sort.
6. 6. swap(arr[j], arr[j + 1]); — C++ built-in swap function exchanges the two values. This is cleaner than using a temporary variable.
7. 7. if (!swapped) break; — if no swaps happened in a complete pass, the array is sorted. This optimization can save a lot of time on nearly-sorted data.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

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

    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Bubble Sort Visualized (YouTube)
• Sorting Algorithms for Beginners (GeeksforGeeks)
• Sort the Array (Codeforces)