Bubble Sort

#How does it work?

Bubble sort walks through the array again and again, comparing elements that sit next to each other. If the left one is larger than the right one, it swaps them.

At the end of every pass, the largest element of the unsorted part rises to the end of the array like a bubble in water and settles into its final place. That is where the name comes from.

If a whole pass makes no swaps, the array is sorted and the algorithm can stop early.

#Live animation

for i = 0 to n - 2
  swapped = false
  for j = 0 to n - i - 2
    if a[j] > a[j + 1]
      swap(a[j], a[j + 1]); swapped = true
  if not swapped: break

#Step by step

1. 01Start at the beginning of the array and compare the first two elements.
2. 02If the left element is larger than the right one, swap them.
3. 03Move one position to the right and compare the next pair; continue until the end.
4. 04When the pass ends, the largest element is at the far right. Ignore it in the next pass.
5. 05Repeat until a pass makes no swaps or there is nothing left to sort.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def bubble_sort(a: list[int]) -> None:
    n = len(a)
    for i in range(n - 1):
        swapped = False
        # After pass i, the last i elements are already in place.
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:  # no swaps: already sorted
            break


numbers = [5, 1, 4, 2, 8, 3]
bubble_sort(numbers)
print(*numbers)

#Complexity

The O(n) best case applies when the array is already sorted and the early exit (swapped flag) is used: a single pass makes n-1 comparisons. A reversed array needs about n²/2 comparisons and as many swaps.

#When to use it?

Bubble sort is great for learning: it shows comparisons, swaps and loop invariants very clearly. In real projects it is slow on large data; merge sort, quick sort or your language's built-in sort are better choices. It can still be reasonable for very small or nearly sorted arrays.

#Practice

Log in to answer questions and save your progress.