Bubble Sort

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

Properties

• Stable
• O(1) extra space
• 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 above to restart the animations in a row, a column, or the entire table.
• Click directly on an animation image to start or restart it.
• Click on a problem size number to reset all animations.

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.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.