1
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – chatton Aug 22 '17 at 15:02
3
\$\begingroup\$

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\$:

enter image description here

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
\$\endgroup\$
  • \$\begingroup\$ So in other words, Bubble sort is slow and nothing can be done about it? \$\endgroup\$ – Lukasz Salitra Aug 22 '17 at 15:07
  • \$\begingroup\$ @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. \$\endgroup\$ – alecxe Aug 22 '17 at 15:10
  • \$\begingroup\$ @LukaszSalitra posted a bit optimized version - check it out - will post my benchmark results soon. \$\endgroup\$ – alecxe Aug 22 '17 at 15:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Lukasz Salitra Aug 22 '17 at 15:45
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – alecxe Aug 22 '17 at 15:48
3
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.