Sorting

Bubble Sort

A simple, stable sorting algorithm that repeatedly compares adjacent elements and swaps them when they are out of order.

Bubble sort is one of the most recognizable beginner sorting algorithms because its process is easy to see: compare neighbors, swap when needed, finish a full pass, and repeat. With each pass, the largest remaining value “bubbles” to the end.

It is not the fastest algorithm for large inputs, but it is useful for teaching comparison logic, loop structure, and the idea of progress through repeated passes.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Repeatedly compare neighboring elements and swap them if they are out of order.

Progress per Pass

After each full pass, the largest unsorted value moves to its final position at the end.

Optimization

If one full pass makes no swaps, the array is already sorted and the algorithm can stop early.

Teaching Value

Bubble sort is great for visualizing repeated comparisons, swaps, and pass-by-pass progress.

Key Idea

Bubble sort works by scanning the array from left to right and comparing each pair of adjacent values. If a pair is in the wrong order, the values are swapped.

The important mental model is: small values move left gradually, while large values keep bubbling rightward until they settle at the end.

Visualization

This visualization emphasizes the repeated pass structure of bubble sort: adjacent comparison, swap when needed, finish the pass, then shrink the unsorted region. It also helps learners notice when the early-exit condition applies.

How It Works

Compare Neighbors

Look at two adjacent elements in the array.

Swap if Needed

If the left value is greater than the right value, swap them.

Complete the Pass

Continue across the array until the largest remaining value reaches the end.

Repeat or Stop

Start another pass on the shorter unsorted region, or stop early if no swaps occurred.

Why It Matters

Easy to Trace

Bubble sort is one of the easiest algorithms to follow step by step because every action is local and visible.

Loop Practice

It gives beginners a good introduction to nested loops, comparison logic, and swap operations.

Optimization Insight

The early-exit condition teaches that algorithms can sometimes detect when further work is unnecessary.

Comparison Point

Bubble sort creates a useful baseline for comparing later sorts like insertion sort, selection sort, and merge sort.

Pseudocode

This pseudocode shows the full bubble sort process with the early-exit optimization:

for i from 0 to n - 2:
    swapped = false

    for j from 0 to n - 2 - i:
        if A[j] > A[j + 1]:
            swap A[j], A[j + 1]
            swapped = true

    if swapped == false:
        break

The important detail is that each outer pass places one more large element into its final position, and the algorithm can stop early when a full pass makes no swaps.

Performance

Time Complexity

Best case: O(n) with early-exit optimization
Average case: O(n²)
Worst case: O(n²)

Space & Stability

Extra space: O(1)
In-place: Yes
Stable: Yes

Bubble sort is usually not chosen for large datasets, but its repetitive structure makes it especially useful for learning.

Common Mistakes

Wrong Loop Bounds

Many learners compare too far into the already sorted end of the array instead of shrinking the range after each pass.

Forgetting Early Exit

If you never check whether a pass made zero swaps, you miss the best-case O(n) improvement.

Confusing Passes and Comparisons

One full pass contains many adjacent comparisons. A pass is not the same thing as a single comparison.

Assuming It Scales Well

Bubble sort is simple, but its quadratic time makes it inefficient on large random inputs.

Outcome

After this lesson, learners should be able to explain how adjacent swaps make large values bubble to the end, trace multiple passes correctly, understand when early exit applies, and read or write basic bubble sort pseudocode.

Back to Home