Animated Sorting Algorithm Demo: Bubble Sort

Algorithm

for i = 1:n,
    for j = n:i+1, if a[j] < a[j-1], swap a[j,j-1]
    invariant: a[1..i] in final position
    if no swaps this iteration, stop
end
        

Properties

• Stable
• In place: O(1) extra space
• Worst case O(n²) comparisons and swaps
• Adaptive: O(n) when nearly sorted

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).

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

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

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.