How Bubble Sort Works

Bubble sort uses nested loops to repeatedly pass through the array, comparing adjacent elements and swapping them when needed.

The Algorithm

Here’s the pseudocode:

for i from 0 to n-1
  for j from 0 to n-i-1
    if array[j] > array[j+1]
      swap(array[j], array[j+1])

Step-by-Step Example

Let’s sort [5, 2, 8, 1, 9]:

Pass 1:

• Compare 5 and 2: 5 > 2, swap → [2, 5, 8, 1, 9]
• Compare 5 and 8: 5 < 8, no swap → [2, 5, 8, 1, 9]
• Compare 8 and 1: 8 > 1, swap → [2, 5, 1, 8, 9]
• Compare 8 and 9: 8 < 9, no swap → [2, 5, 1, 8, 9]
• Largest element (9) is now in place

Pass 2:

• Compare 2 and 5: 2 < 5, no swap → [2, 5, 1, 8, 9]
• Compare 5 and 1: 5 > 1, swap → [2, 1, 5, 8, 9]
• Compare 5 and 8: 5 < 8, no swap → [2, 1, 5, 8, 9]
• Second largest (8) is now in place

Pass 3:

• Compare 2 and 1: 2 > 1, swap → [1, 2, 5, 8, 9]
• Compare 2 and 5: 2 < 5, no swap → [1, 2, 5, 8, 9]
• Third largest (5) is now in place

Pass 4:

• Compare 1 and 2: 1 < 2, no swap → [1, 2, 5, 8, 9]
• Array is sorted!

Visual Representation

Interactive Diagram

This interactive diagram requires JavaScript to be enabled.

Steps:

1. Compare 5 and 2: 5 > 2, need to swap
2. Swap 5 and 2 → [2, 5, 8, 1, 9]
3. Compare 8 and 1: 8 > 1, need to swap
4. After multiple passes, array is sorted

Key Points

1. Outer loop: Runs n-1 times (one less than array length)
2. Inner loop: Shrinks each pass (n-i-1 comparisons)
3. Comparison: Always compares adjacent elements
4. Swap: Only swaps if left > right
5. Result: Largest unsorted element bubbles to the end each pass

Why n-i-1?

After each pass, the largest unsorted element is in its correct position. So we don’t need to compare it again. That’s why the inner loop goes from 0 to n-i-1.

What’s Next?

Now that you understand how it works, let’s see it in action with an interactive visualization.