Bubble sort, sometimes shortened to bubblesort, also known as exchange
sort, is a simple
sorting algorithm. It works by repeatedly stepping through the list to
be sorted, comparing two items at a time and
swapping them if they are in
the wrong order. The pass through the list is repeated until no swaps
are needed, which means the list is sorted. The algorithm gets its name from
the way smaller elements "bubble" to the top (i.e. the beginning) of the
list via the swaps. Because it only uses comparisons to operate on elements,
it is a comparison
sort. This is the easiest comparison sort to implement.
def bubblesort(l):
"Sorts l in place and returns it."
for passesLeft in range(len(l)-1, 0, -1):
for index in range(passesLeft):
if l[index] < l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l
|