Python bubble sort algorithm

Question

How can this algorithm be improved? I mean, a list with 3000 items takes about 5 seconds to sort, according to Sublime Text. Using Python's sorted function is immediate.

from random import randint def bubble_sort(iterable): while True: corrected = False for item in range(0, len(iterable) - 1): if iterable[item] > iterable[item + 1]: iterable[item], iterable[item + 1] = iterable[item + 1], iterable[item] corrected = True if not corrected: return iterable if __name__ == '__main__': random_list = [randint(0, 100) for _ in range(3000)] print(bubble_sort(random_list)) 

Answer 1

Python's sorted() uses an adaptive sorting algorithm called "timsort" (from its author name Tim Peters), which has worst case complexity of \$O(n log n)\$.

Bubble Sort on the other hand has best, worst and average time complexity of \$O(n ^ 2)\$ which is much worse than \$O(n log n)\$ with growing \$n\$:

In other words, the Bubble Sort sorting algorithm is inefficient by definition.

We can though still apply some optimizations - adjust the end of the working range - skipping every last item on each iteration since it is already in place:

def bubble_sort_new(iterable): swapped = True while swapped: swapped = False end = len(iterable) - 1 for item in range(0, end): if iterable[item] > iterable[item + 1]: iterable[item], iterable[item + 1] = iterable[item + 1], iterable[item] swapped = True end -= 1 return iterable 

My timeit results:

In [1]: import random In [2]: random_list = [randint(0, 100) for _ in range(3000)] In [3]: %timeit -r 100 bubble_sort(random_list) 1000 loops, best of 100: 402 µs per loop In [4]: %timeit -r 100 bubble_sort_new(random_list) 1000 loops, best of 100: 382 µs per loop 

Answer 2

This is a particularly inefficient implementation, because on each iteration the whole list is iterated when the algorithm ensures that the highest positions are already sorted. This minimal improvement allows to reduce the run time by about 30%:

def bubble_sort(iterable): for l in range(len(iterable)-1, 2, -1): corrected = False for item in range(0, l): # reduce the size of the list to sort by 1 on each pass if iterable[item] > iterable[item + 1]: iterable[item], iterable[item + 1] = iterable[item + 1], iterable[item] corrected = True if not corrected: break return iterable 

Ok, this is still clearly bad ,but bubble sort is known to be easy to implement, not to be efficient.

You will find more references and a slightly better optimization on wikipedia