Working Principle of Bubble Sort

We've grasped the basic idea: compare two neighbors and swap them if they're out of order. But how does this simple, tiny operation manage to sort an entire, jumbled array?

This is where the "working principle" of Bubble Sort comes in. It’s not about just one or two swaps; it's about a systematic, repeated process that brings the entire list into order, one pass at a time. Think of it as a bouncer at a club, checking IDs. Instead of just checking one pair, the bouncer walks the entire length of the line. On the first pass, they ensure the single "heaviest" or largest item gets moved all the way to its final spot at the end.

Then, they do it again, but this time they stop one person short, as the last spot is already correct. This method of performing multiple "passes" over the list, with each pass guaranteeing that one more element finds its permanent home, is the core engine that makes Bubble Sort work. In this section, we'll break down this step-by-step process.

3.1: Step-by-Step Execution Process

Now that we understand the basic concept of comparing adjacent elements, let's see the Bubble Sort algorithm in action. The working principle is best understood as a series of "passes" through the array.

Think of it this way: the algorithm's mission in each pass is to find the largest unsorted element and "bubble" it up to its correct final position at the end of the list.

Let's take a simple unsorted array to demonstrate this step-by-step execution process:

Array:
[6, 5, 3, 1, 8, 7, 2, 4]

3.1.1: Passes and Comparisons in Each Iteration

Pass 1: The First Sweep (n=8, n-1=7 comparisons)

The algorithm will compare every adjacent pair, starting from the beginning. The goal is to "bubble" the largest value to the very end.

Start:
[6, 5, 3, 1, 8, 7, 2, 4]

Compare [6, 5]: Is 6 > 5? Yes. Swap.
Array becomes: [5, 6, 3, 1, 8, 7, 2, 4]

Compare [6, 3]: Is 6 > 3? Yes. Swap.
Array becomes: [5, 3, 6, 1, 8, 7, 2, 4]

Compare [6, 1]: Is 6 > 1? Yes. Swap.
Array becomes: [5, 3, 1, 6, 8, 7, 2, 4]

Compare [6, 8]: Is 6 > 8? No. Do nothing.
Array remains: [5, 3, 1, 6, 8, 7, 2, 4]

Compare [8, 7]: Is 8 > 7? Yes. Swap.
Array becomes: [5, 3, 1, 6, 7, 8, 2, 4]

Compare [8, 2]: Is 8 > 2? Yes. Swap.
Array becomes: [5, 3, 1, 6, 7, 2, 8, 4]

Compare [8, 4]: Is 8 > 4? Yes. Swap.
Array becomes: [5, 3, 1, 6, 7, 2, 4, 8]

End of Pass 1: The largest element, 8, has "bubbled" to its correct final position. The array is now split into an unsorted part and a sorted part.

Result:
[5, 3, 1, 6, 7, 2, 4 | 8]

Pass 2: The Second Sweep (n-2=6 comparisons)

We repeat the process, but we can now ignore the last element (8), which we know is sorted.

Start:
[5, 3, 1, 6, 7, 2, 4 | 8]

Compare [5, 3]: Is 5 > 3? Yes. Swap.
Array becomes: [3, 5, 1, 6, 7, 2, 4 | 8]

Compare [5, 1]: Is 5 > 1? Yes. Swap.
Array becomes: [3, 1, 5, 6, 7, 2, 4 | 8]

Compare [5, 6]: Is 5 > 6? No. Do nothing.
Array remains: [3, 1, 5, 6, 7, 2, 4 | 8]

Compare [6, 7]: Is 6 > 7? No. Do nothing.
Array remains: [3, 1, 5, 6, 7, 2, 4 | 8]

Compare [7, 2]: Is 7 > 2? Yes. Swap.
Array becomes: [3, 1, 5, 6, 2, 7, 4 | 8]

Compare [7, 4]: Is 7 > 4? Yes. Swap.
Array becomes: [3, 1, 5, 6, 2, 4, 7 | 8]

End of Pass 2: The next-largest element, 7, is now in place. The sorted portion grows.

Result:
[3, 1, 5, 6, 2, 4 | 7, 8]

Pass 3: The Third Sweep (n-3=5 comparisons)

We now ignore the last two elements.

Start:
[3, 1, 5, 6, 2, 4 | 7, 8]

Compare [3, 1]: Is 3 > 1? Yes. Swap.
Array becomes: [1, 3, 5, 6, 2, 4 | 7, 8]

Compare [3, 5]: Is 3 > 5? No. Do nothing.
Array remains: [1, 3, 5, 6, 2, 4 | 7, 8]

Compare [5, 6]: Is 5 > 6? No. Do nothing.
Array remains: [1, 3, 5, 6, 2, 4 | 7, 8]

Compare [6, 2]: Is 6 > 2? Yes. Swap.
Array becomes: [1, 3, 5, 2, 6, 4 | 7, 8]

Compare [6, 4]: Is 6 > 4? Yes. Swap.
Array becomes: [1, 3, 5, 2, 4, 6 | 7, 8]

End of Pass 3: The element 6 is now in its correct position.

Result:
[1, 3, 5, 2, 4 | 6, 7, 8]

Pass 4: The Fourth Sweep (n-4=4 comparisons)

Start:
[1, 3, 5, 2, 4 | 6, 7, 8]

Compare [1, 3]: Is 1 > 3? No. Do nothing.
Compare [3, 5]: Is 3 > 5? No. Do nothing.

Compare [5, 2]: Is 5 > 2? Yes. Swap.
Array becomes: [1, 3, 2, 5, 4 | 6, 7, 8]

Compare [5, 4]: Is 5 > 4? Yes. Swap.
Array becomes: [1, 3, 2, 4, 5 | 6, 7, 8]

End of Pass 4: The element 5 is now in its correct position.

Result:
[1, 3, 2, 4 | 5, 6, 7, 8]

Pass 5: The Fifth Sweep (n-5=3 comparisons)

Start:
[1, 3, 2, 4 | 5, 6, 7, 8]

Compare [1, 3]: Is 1 > 3? No. Do nothing.

Compare [3, 2]: Is 3 > 2? Yes. Swap.
Array becomes: [1, 2, 3, 4 | 5, 6, 7, 8]

Compare [3, 4]: Is 3 > 4? No. Do nothing.
Array remains: [1, 2, 3, 4 | 5, 6, 7, 8]

End of Pass 5: The element 4 is now in its correct position.

Result:
[1, 2, 3 | 4, 5, 6, 7, 8]

A Quick Note: The Array is Already Sorted!

Notice that at the end of Pass 5, the entire array
[1, 2, 3, 4, 5, 6, 7, 8]
is now fully sorted.

However, the "naive" Bubble Sort algorithm doesn't know this! It is programmed to run n-1 (or 7) passes, no matter what. It will continue to run, even though no more swaps are needed. This is a key source of its inefficiency.

Pass 6: The Sixth Sweep (n-6=2 comparisons)

Start:
[1, 2, 3 | 4, 5, 6, 7, 8]

Compare [1, 2]: Is 1 > 2? No. Do nothing.
Compare [2, 3]: Is 2 > 3? No. Do nothing.

Array remains:
[1, 2, 3 | 4, 5, 6, 7, 8]

Pass 7: The Final Sweep (n-7=1 comparison)

Start:
[1, 2 | 3, 4, 5, 6, 7, 8]

Compare [1, 2]: Is 1 > 2? No. Do nothing.

Array remains:
[1, 2 | 3, 4, 5, 6, 7, 8]

Final Sorted Array

[1, 2, 3, 4, 5, 6, 7, 8]

Working Principle Summary

This entire working principle of Bubble Sort is built on these two key ideas:

Pass

A "pass" is one full iteration (the outer loop in C programming) that scans the unsorted part of the array. For our array with n=8 elements, the un-optimized algorithm will always make n-1 = 7 passes.

Comparisons

"Comparisons" are the individual checks (the inner loop) between adjacent elements.

• In Pass 1 → n-1 = 7 comparisons
• In Pass 2 → n-2 = 6
• Continuing until
• Final Pass → 1 comparison

This methodical "bubble" action is simple to visualize, but as you can see, it involves many comparisons and iterations. The fact that it continued running for two full passes (Pass 6 and 7) after the array was already sorted is what directly impacts its performance. We'll explore this (and how to fix it) when we implement the code and analyze its complexity.