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

How to use: Press "Play all", or choose the    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(n2) comparisons and swaps
  • Adaptive: O(n) when nearly sorted

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

JavaJavaScriptC++PHPPythonRubyC#