|
|
|
|
|
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
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).
above to restart
the animations in a row, a column, or the entire table.
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.
Comments
— posted by someone on 27-Jan-2010
— posted by someone on 13-Jan-2010
— posted by someone on 20-Dec-2009
— posted by someone on 8-Dec-2009