# Python bubble sort algorithm

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))

• bubble sort is an extremely inefficient sorting algorithm, it has a time complexity of O(N^2) whereas the built in sorted function uses the Timsort algorithm (last time I checked) which has a time complexity of O(n log n) Aug 22 '17 at 15:02

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

• So in other words, Bubble sort is slow and nothing can be done about it? Aug 22 '17 at 15:07
• @LukaszSalitra yes, it is inefficient by definition, but let me see if we can apply some micro-optimizations - I doubt they will change the overall picture though. Thanks. Aug 22 '17 at 15:10
• @LukaszSalitra posted a bit optimized version - check it out - will post my benchmark results soon. Aug 22 '17 at 15:43
• Will do! I am not sure how accurate Sublime's timer is, but it seems to have reduced the script running time by about 0.3s. Aug 22 '17 at 15:45
• @LukaszSalitra yeah, I see some improvement there as well, posted timeit results. It is still, of course, much slower than sorted(), and it will stay this way, just a slow algorithm. Aug 22 '17 at 15:48

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