Bubble Sort

Say you have a few numbers in a list. You want them in order, smallest to largest. How would you even start? The simplest idea is to walk through the list and keep swapping neighbours that are out of order. That simple idea is exactly what bubble sort does. It is usually the first sorting method anyone learns.

🫧 What Is Bubble Sort?

Bubble sort is a sorting method that walks through the list again and again. Each time it looks at every pair of neighbouring items and swaps them when they are in the wrong order.

Think about the name for a second. Imagine bubbles in a glass of soda. The big bubbles slowly rise to the top, right? In bubble sort the biggest unsorted number behaves the same way. After one full walk through the list, the largest item has moved all the way to the end. Then the next largest settles just before it, and so on.

So the core action is tiny and easy:

• Look at two items sitting next to each other.
• If the left one is bigger than the right one, swap them.
• Move one step to the right and do it again.

You repeat this whole walk again and again until no swaps are needed. When a full walk happens with zero swaps, the list is already sorted.

🎯 Why Learn It?

Here is the honest part. Bubble sort is slow for big lists. Real software almost never uses it. The pain it solves is not speed. It is understanding.

• It teaches you what sorting actually means: compare, then swap.
• The logic is short, so you can trace it by hand and really see it work.
• It builds the base you need before harder sorts like merge sort or quick sort.

So treat bubble sort as a learning tool. You learn the idea here. Then you move to faster sorts for real work.

🔍 A Small Trace

Let us sort this list: [5, 1, 4, 2]. We want it from smallest to largest.

In the first pass we compare each neighbouring pair from left to right.

• Compare 5 and 1. Five is bigger, so swap. List becomes [1, 5, 4, 2].
• Compare 5 and 4. Five is bigger, so swap. List becomes [1, 4, 5, 2].
• Compare 5 and 2. Five is bigger, so swap. List becomes [1, 4, 2, 5].

See what happened? The biggest number, 5, bubbled all the way to the end. That last spot is now locked, meaning it is in its final place.

The second pass works on [1, 4, 2]. We ignore the locked 5.

• Compare 1 and 4. Already in order, no swap.
• Compare 4 and 2. Four is bigger, so swap. List becomes [1, 2, 4, 5].

Now 4 is locked too. The third pass checks 1 and 2. They are already in order, so no swaps happen. Zero swaps means we can stop early. The list is sorted: [1, 2, 4, 5].

This picture sums up one full pass:

📝 Steps to Bubble Sort a List

Before we write code, let us put the plan in plain steps.

1. Start at the beginning of the list.
2. Compare the current item with the one right after it.
3. If the current item is bigger, swap the two.
4. Move one step to the right and repeat the compare-and-swap until you reach the end of the unsorted part.
5. After a full pass, the largest unsorted item is now at the end, so shrink the unsorted part by one.
6. If a whole pass finished with no swaps, stop early. The list is sorted.
7. Otherwise repeat the passes until the list is sorted.

That step 6 is the early exit. If one pass does no swaps at all, then nothing is out of order, so there is no point checking again.

💻 Bubble Sort in Code

Here is bubble sort with the early-exit optimization. The outer loop counts the passes. The inner loop does the compares and swaps. A simple flag remembers whether any swap happened in the current pass. If the flag stays false, we break out early.

#include <stdio.h>

// Sort the array from smallest to largest using bubble sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0; // did we swap anything this pass?

        // Last i items are already in place, so stop earlier each time
        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; // no swaps means it is already sorted
    }
}

int main() {
    int arr[] = {5, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

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

1 2 4 5

#include <iostream>
using namespace std;

// Sort the array from smallest to largest using bubble sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // did we swap anything this pass?

        // Last i items are already in place, so stop earlier each time
        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; // no swaps means it is already sorted
    }
}

int main() {
    int arr[] = {5, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

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

1 2 4 5

public class BubbleSort {

    // Sort the array from smallest to largest using bubble sort
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false; // did we swap anything this pass?

            // Last i items are already in place, so stop earlier each time
            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 = true;
                }
            }

            if (!swapped) break; // no swaps means it is already sorted
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2};

        bubbleSort(arr);

        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

1 2 4 5

# Sort the list from smallest to largest using bubble sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False  # did we swap anything this pass?

        # Last i items are already in place, so stop earlier each time
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        if not swapped:  # no swaps means it is already sorted
            break


numbers = [5, 1, 4, 2]
bubble_sort(numbers)
print(numbers)

[1, 2, 4, 5]

// Sort the array from smallest to largest using bubble sort
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false; // did we swap anything this pass?

    // Last i items are already in place, so stop earlier each time
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    if (!swapped) break; // no swaps means it is already sorted
  }
}

const numbers = [5, 1, 4, 2];
bubbleSort(numbers);
console.log(numbers);

[ 1, 2, 4, 5 ]

⏱️ Time and Space Complexity

Let us break down how much work bubble sort does. Here n is the number of items in the list.

• In the worst case the list is in reverse order. Every pair gets compared and swapped, which is about n times n work. That is O(n^2) time.
• In the best case the list is already sorted. The early exit kicks in after one pass, so it is O(n) time.
• It uses no extra list, just a temporary variable for the swap. So it is O(1) space.

Bubble sort is also stable. A stable sort keeps equal items in the same order they started in. This happens because we only swap when the left item is strictly bigger than the right one.

🐞 Common Mistakes

A few small slips trip people up with bubble sort:

• Letting the inner loop run all the way to the end every time. Use n - 1 - i so it stops before the part that is already sorted.
• Forgetting the early-exit flag. Without it, an already sorted list still does every pass for no reason.
• Going one step too far with arr[j + 1] and reading past the end of the list. The inner loop must stop at n - 1 - i, not n.
• Swapping when the items are equal. Swap only when the left is strictly bigger, otherwise you lose stability.

🧩 What You’ve Learned

✅ Bubble sort compares each pair of neighbours and swaps them when they are out of order.

✅ After every full pass the largest unsorted item bubbles to the end and gets locked in place.

✅ An early-exit flag stops the sort as soon as a pass makes no swaps, giving an O(n) best case.

✅ Its time is O(n^2) in the average and worst case, its space is O(1), and it is a stable sort.

✅ It is mainly a learning tool, so real programs use faster sorts for big lists.

🚀 What’s Next?

• Selection Sort
• Introduction to Sorting