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]

1. Compare [6, 5**]**: Is 6 > 5? Yes. Swap.
   • Array becomes: [5, 6, 3, 1, 8, 7, 2, 4]
2. Compare [6, 3**]**: Is 6 > 3? Yes. Swap.
   • Array becomes: [5, 3, 6, 1, 8, 7, 2, 4]
3. Compare [6, 1**]**: Is 6 > 1? Yes. Swap.
   • Array becomes: [5, 3, 1, 6, 8, 7, 2, 4]
4. Compare [6, 8**]**: Is 6 > 8? No. Do nothing.
   • Array remains: [5, 3, 1, 6, 8, 7, 2, 4]
5. Compare [8, 7**]**: Is 8 > 7? Yes. Swap.
   • Array becomes: [5, 3, 1, 6, 7, 8, 2, 4]
6. Compare [8, 2]: Is 8 > 2? Yes. Swap.
   • Array becomes: [8, 2]
7. 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]

1. Compare [5, 3**]**: Is 5 > 3? Yes. Swap.
   • Array becomes: [3, 5, 1, 6, 7, 2, 4 | 8]
2. Compare [5, 1**]**: Is 5 > 1? Yes. Swap.
   • Array becomes: [3, 1, 5, 6, 7, 2, 4 | 8]
3. Compare [5, 6**]**: Is 5 > 6? No. Do nothing.
   • Array remains: [3, 1, 5, 6, 7, 2, 4 | 8]
4. Compare [6, 7**]**: Is 6 > 7? No. Do nothing.
   • Array remains: [3, 1, 5, 6, 7, 2, 4 | 8]
5. Compare [7, 2**]**: Is 7 > 2? Yes. Swap.
   • Array becomes: [3, 1, 5, 6, 2, 7, 4 | 8]
6. 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]

1. Compare [3, 1**]**: Is 3 > 1? Yes. Swap.
   • Array becomes: [1, 3, 5, 6, 2, 4 | 7, 8]
2. Compare [3, 5**]**: Is 3 > 5? No. Do nothing.
   • Array remains: [1, 3, 5, 6, 2, 4 | 7, 8]
3. Compare [5, 6**]**: Is 5 > 6? No. Do nothing.
   • Array remains: [1, 3, 5, 6, 2, 4 | 7, 8]
4. Compare [6, 2**]**: Is 6 > 2? Yes. Swap.
   • Array becomes: [1, 3, 5, 2, 6, 4 | 7, 8]
5. 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]

1. Compare [1, 3**]**: Is 1 > 3? No. Do nothing.
2. Compare [3, 5**]**: Is 3 > 5? No. Do nothing.
3. Compare [5, 2**]**: Is 5 > 2? Yes. Swap.
   • Array becomes: [1, 3, 2, 5, 4 | 6, 7, 8]
4. 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]

1. Compare [1, 3**]**: Is 1 > 3? No. Do nothing.
2. Compare [3, 2**]**: Is 3 > 2? Yes. Swap.
   • Array becomes: [1, 2, 3, 4 | 5, 6, 7, 8]
3. 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]

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

End of Pass 6: The element 3 is confirmed in its position. The algorithm still doesn't know the array is sorted.

• Result: [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]

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

End of Pass 7: The element 2 is confirmed. The last remaining element, 1, is sorted by default.

• 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, we made n-1 = 7 comparisons. In Pass 2, we made n-2 = 6, and so on, all the way down to 1 comparison in the last pass.

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.