Python'ssorted() 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 isinefficient 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

Mytimeit results:

In [1]: import randomIn [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 loopIn [4]: %timeit -r 100 bubble_sort_new(random_list)1000 loops, best of 100: 382 µs per loop

• \$\begingroup\$So in other words, Bubble sort is slow and nothing can be done about it?\$\endgroup\$

  Luke

  – Luke

  2017-08-22 15:07:39 +00:00

  CommentedAug 22, 2017 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

  – alecxe

  2017-08-22 15:10:10 +00:00

  CommentedAug 22, 2017 at 15:10
• \$\begingroup\$@LukaszSalitra posted a bit optimized version - check it out - will post my benchmark results soon.\$\endgroup\$

  alecxe

  – alecxe

  2017-08-22 15:43:31 +00:00

  CommentedAug 22, 2017 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\$

  Luke

  – Luke

  2017-08-22 15:45:54 +00:00

  CommentedAug 22, 2017 at 15:45
• 1
  \$\begingroup\$@LukaszSalitra yeah, I see some improvement there as well, postedtimeit results. It is still, of course, much slower thansorted(), and it will stay this way, just a slow algorithm.\$\endgroup\$

  alecxe

  – alecxe

  2017-08-22 15:48:03 +00:00

  CommentedAug 22, 2017 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 onwikipedia

• python
• algorithm
• sorting