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] &gt; 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))
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] &gt; 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