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