How Bubble Sort Works (And Why It Takes Its Time)

What is Sorting?

At its core, sorting is just the process of arranging a messy collection of items into a specific, meaningful order.

Here are two examples of sorting, we go through every day life:

• Numerical Order: Arranging numbers from smallest to largest (1, 2, 3…) or largest to smallest (99, 98, 97…).

• Alphabetical Order: Arranging words or strings from A to Z (like a phonebook contact list) or Z to A.

Why do we code to Sort through?

Computers don’t sort data just to make it look neat. They do it because sorted data is incredibly fast to work with.

Think about trying to find a specific word in a massive dictionary. If the dictionary were printed in a completely random order, you would have to read every single page from start to finish just to find one definition. Because it is strictly sorted from A to Z, your brain instantly knows how to skip straight to the section you need.

In the exact same way, sorting turns a chaotic mess of data into an organized system that algorithms can search through, analyze, and process in milliseconds. Bubble Sort is just one of many different strategies, or algorithms, we use to get that data in order.

What is this Bubble Sort?

Imagine you have a playlist of songs, and you want to order them from your absolute least favorite to your ultimate favorite. Bubble Sort works like a lazy listener. It compares just the first two tracks. If track two is better, they swap places. Then it compares track two and three, swapping again if needed. By the time you listen all the way to the end of the playlist, your #1 favorite song has naturally drifted, or bubbled all the way to the very top.

In computer science, Bubble Sort (sometimes referred to as sinking sort) is a fundamental, comparison-based sorting algorithm. It operates on a simple iterative principle: it repeatedly steps through a data structure, compares adjacent elements, and swaps them if they are in the wrong order.

While we speak about Bubble Sort, we have to keep three point in mind!

• The Mechanics of the Passes:

The algorithm gets its name because smaller or larger elements “bubble” to the top of the data structure after each iteration (or “pass”). During a single pass, the algorithm runs a loop from index 0 to (n-1). With each comparison, the larger value is pushed forward. Consequently, each full pass guarantees that the next highest unsorted value settles into its final, permanently correct position at the end of the array

• Time Complexity: The Cost of Nested Loops

Bubble Sort relies on two nested loops: an outer loop to track the number of passes, and an inner loop to compare adjacent items.

• Worst-Case Complexity (O($n^2$)): Occurs when the input array is sorted in completely reverse order. The algorithm must perform the maximum number of comparisons and swaps, resulting in a quadratic time scale ($\frac{n(n-1)}{2}$ total comparisons).
• Average-Case Complexity (O($n^2$)): Occurs when the data is randomly distributed.
• Best-Case Complexity (O(n)): Occurs when the array is already fully sorted. If optimized with a boolean flag that tracks whether a swap happened during a pass, the algorithm can realize the array is sorted and terminate early after just one single pass of (n-1) comparisons.

• Space Complexity and Memory Efficiency

Bubble Sort is classified as an in-place algorithm. It manipulates the data directly inside the original array pointer without allocating auxiliary memory that scales with the input size. Because it only requires a single temporary variable to handle the swapping mechanism, its space complexity is a highly efficient O(1) (constant space).

Step-by-Step Example

Let’s sort a small, unsorted array of numbers in ascending order: [5, 1, 4, 2, 8, 0]

• Step 1: The First Big Walkthrough

Starting array : [5, 1, 4, 2, 8, 0]

1. Compare 5 and 1 : Is 5 > 1? Yes -> Swap -> [1, 5, 4, 2, 8, 0]
2. Compare 5 and 4 : Is 5 > 4? Yes -> Swap -> [1, 4, 5, 2, 8, 0]
3. Compare 5 and 2 : Is 5 > 2? Yes -> Swap -> [1, 4, 2, 5, 8, 0]
4. Compare 5 and 8 : Is 5 > 8? No -> Keep -> [1, 4, 2, 5, 8, 0]
5. Compare 8 and 0 : Is 8 > 0? Yes -> Swap -> [1, 4, 2, 5, 0, 8]

End of Pass 1: The largest number (8) has successfully bubbled to the very end. It is now locked into place.

• Step 2: Finding the Next Largest

Active boundary: [1, 4, 2, 5, 0] (We ignore index 5 where 8 is)

1. Compare 1 and 4: Is 1 > 4? No -> Keep -> ([1, 4, 2, 5, 0, 8])
2. Compare 4 and 2: Is 4 > 2? Yes -> Swap -> ([1, 2, 4, 5, 0, 8])
3. Compare 4 and 5: Is 4 > 5? No -> Keep -> ([1, 2, 4, 5, 0, 8])
4. Compare 5 and 0: Is 5 > 0? Yes -> Swap -> ([1, 2, 4, 0, 5, 8])

End of Pass 2: The next largest number (5) is locked into place.

• Step 3: Shrinking the Window

Active boundary: [1, 2, 4, 0] (We now ignore 5 and 8)

1. Compare 1 and 2: Is 1 > 2? No -> Keep -> ([1, 2, 4, 0, 5, 8])
2. Compare 2 and 4: Is -> 2 > 4? No -> Keep -> ([1, 2, 4, 0, 5, 8])
3. Compare 4 and 0: Is 4 > 0? Yes -> Swap ->([1, 2, 0, 4, 5, 8])

End of Pass 3: The number 4 is locked into place.

• Step 4: Getting Closer

Active boundary: [1, 2, 0]

1. Compare 1 and 2: Is 1 > 2? No -> Keep -> ([1, 2, 0, 4, 5, 8])
2. Compare 2 and 0: Is 2 > 0? Yes -> Swap -> ([1, 0, 2, 4, 5, 8])

End of Pass 4: The number 2 is locked into place.

• Pass 5: The Final Swap

Active boundary: [1, 0]

1. Compare 1 and 0: Is 1 > 0? Yes -> Swap -> ([0, 1, 2, 4, 5, 8])

End of Pass 5: The number 1 is locked into place.

• Pass 6: The Safety Check

Active boundary: [0]

The algorithm does one final look at the remaining unsorted element. Since there is only one element left, or because it runs a final check pass and detects zero swaps, it knows the array is officially completely sorted.

Final Sorted Array: [0, 1, 2, 4, 5, 8]

Example:

Following is a program of the general Bubble Sorting. (in C++)

#include <iostream>
#include <vector>
#include <utility> // Required for std::swap

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    
    // Outer loop: controls the number of passes
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        // Inner loop: compares adjacent elements
        // (n - i - 1) stops us from checking already sorted numbers at the end

        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Use standard library swap function
                std::swap(arr[j], arr[j + 1]);
                swapped = true; // Mark that a swap occurred
            }
        }
        
        // Optimization: if no elements were swapped, the array is already sorted
        if (!swapped) {
            break;
        }
    }
}

// Helper function to print the vector layout
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> numbers = {5, 1, 4, 2, 8, 0};
    
    std::cout << "Original Array: ";
    printVector(numbers);
    
    bubbleSort(numbers);
    
    std::cout << "Sorted Array:   ";
    printVector(numbers);
    
    return 0;
}

Using this piece of code, you will be easily be able to sort through a vast variety of number, in Ascending Order.

What do you think, the sorting will look like for the Descending Order?

The amazing thing is-
Almost the whole peice will be very similar to that of the Ascending Order, except the change is-

// Inner loop: compares adjacent elements
for (int j = 0; j < n - i - 1; j++) {
    // Flipped to '<' to push smaller elements to the end of the vector
    if (arr[j] < arr[j + 1]) { 
        std::swap(arr[j], arr[j + 1]);
        swapped = true; 
    }
}

The above peice of code gives the numbers in a Descending Order.

Although usefull, Bubble Sort is QUITE disadvantageous, mainly due to-

• Terrible Time Complexity (O($n^2$))

Because it uses nested loops, the time it takes to sort grows drastically as your dataset gets larger. If you double the size of your array, it takes four times longer to execute. If you have suppose, 10,000 items, it has to perform up to roughly 100,000,000 (one hundred million) comparisons. Other algorithms like Merge Sort or Quick Sort handle this in a fraction of a millisecond using O(n log n) time.

• Way Too Many Swaps

Unlike Selection Sort (which only swaps elements once per pass), Bubble Sort swaps elements continuously. Modifying data in memory over and over again consumes CPU cycles, making it incredibly slow and memory-thrashing in practice.

So, in Conclusion, Bubble Sort is an educational tool, not a practical one. It’s perfect for training your brain to understand loops and swapping mechanics, but highly inefficient for real-world apps with big data.

Tip: Bubble Sort is an educational tool, not a practical one. It’s perfect for training your brain to understand loops and swapping mechanics, but highly inefficient for real-world apps with big data.