A
bubble sort is a simple
sort algorithm that runs in
O(
n2) time and can sort in place. It is one of the simplest
sorting algorithms to understand, but is generally considered too inefficient for serious work sorting large numbers of elements. It is essentially equivalent to
insertion sort --- it compares and swaps the same pairs of elements, just in a different order. Since the insertion sort and bubble sort are so simple, though, they tend to be the most efficient sorting algorithms for sorting small numbers of elements.
The bubble sort algorithm is:
- compare adjacent elements. If the first is greater than the second, swap them.
- do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest (it has "bubbled" to the top).
- repeat the steps for all elements except the last one.
- keep repeating for one fewer element each time, until you have no more pairs to compare.
A simple implementation of bubble sort in Python:
def bubblesort(array, cmp=lambda x, y: x > y):
for i in range( len(array) ):
for j in range( len(array)-1-i ):
if cmp(array[j], array[j+1]):
( array[j], array[j+1] ) = ( array[j+1], array[j] )
A C version is in /C.