Toptal connects the top 3% of freelance developers all over the world.

Bubble Sort

Animation, code, analysis, and discussion of bubble sort on 4 initial conditions.

← Back to all algorithms and initial conditions

0shares

How to use: Press "Play all", or choose the Play button.

Play All	Play animation Random	Play animation Nearly Sorted	Play animation Reversed	Play animation Few Unique

ALGORITHM

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

DISCUSSION

Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

KEY

Black values are sorted.
Gray values are unsorted.
A red triangle marks the algorithm position.

PROPERTIES

Stable
O(1) extra space
O(n²) comparisons and swaps
Adaptive: O(n) when nearly sorted

Preparing for a technical interview? Check out our interview guides.