Compare bubble sort with Python's built-in sort, counting the swaps needed to put a small list in order.
Bubble sort does a fixed number of swaps, and the built-in sort does far fewer and it gets faster on data that is nearly in order.
def bubble_sort(values):
data = list(values)
swaps = 0
for end in range(len(data) - 1, 0, -1):
for i in range(end):
if data[i] > data[i + 1]:
data[i], data[i + 1] = data[i + 1], data[i]
swaps += 1
return data, swaps
the list of six items bubble sort swaps the built-in sort
---------------------- ----------------- --------------
random 9 fewer
already in order 0 0
in reverse order 15 fewer
So what is the difference? Bubble sort always makes the same number of comparisons, which is about n squared over two, no matter what the data looks like. The built-in sort, which is called Timsort, notices the parts that are already in order and leaves them alone, so on data that is nearly sorted it does far less work.
And the swaps are worth counting too, because they are the expensive part. A swap of two items in a list costs real work, and a good sorting algorithm gets the data in order with as few swaps as it can. Bubble sort is bad at this, because a single item may have to travel all the way along the list.
The next question in this topic shows something that is true of merge sort and not of quicksort.