Implement bubble sort in Python

I have written the following code for bubble sort. How can it be optimised?

def bubble_sort(details):
"""compares two consecutive integers in a list and shifts the smaller one to left """
for i in range(len(details)-1):
try:
if details[i] > details[i+1]:
temp = details[i]
details[i]= details[i+1]
details[i+1] = temp
bubble_sort(details)
except IndexError:
return
return details

sort_me = [11,127,56,2,1,5,7,9,11,65,12,24,76,87,123,65,8,32,86,123,67,1,67,92,72,39,49,12, 98,52,45,19,37,22,1,66,943,415,21,785,12,698,26,36,18,97,0,63,25,85,24,94,1501]
print sort_me
print bubble_sort(sort_me)

• Bubble sort can't be optimized! Jan 21, 2018 at 17:27

There are a few things I wanted to talk about.

1. You shouldn't try / except an IndexError as a form of control flow.

An IndexError here would be the programmer's mistake, you should make sure that your code can't even raise an IndexError in the first place by using correct conditions in your loops. You can also removed the try/except sections completely and your code still behaves the same way.

1. Recursion

BubbleSort is an inefficient sorting algorithm when dealing with large inputs. The sheer number of comparisons done with larger inputs will cause some serious problems if you recursively call the function.

With the example input you gave, your function gets called 568 times. I tried sorting a list of double the size and got this

RecursionError: maximum recursion depth exceeded in comparison


Using a more straightforward iterative approach would be much more efficient.

def bubble_sort(details):
"""compares two consecutive integers in a list and shifts the smaller one to left """
for i in range(len(details) - 1):
swapped = False
for j in range(len(details) - 1):
if details[j] > details[j+1]:
temp = details[j]
details[j] = details[j+1]
details[j+1] = temp
swapped = True

if not swapped:
break

return details

sort_me = [11,127,56,2,1,5,7,9,11] * 100 # give it a large input
print sort_me
print bubble_sort(sort_me)


• Consider implementing a version that doesn't modify the original list, think sorted(list) vs list.sort().

• Your current implementation sorts the method in place but also returns the same list. If your method is mutating the list, consider not having a return value (or returning None instead).

Hopefully this was useful for you!

Python has in place swap available:

temp = details[i]
details[i]= details[i+1]
details[i+1] = temp


will become:

details[i], details[i+1] = details[i+1], details[i]


Instead of recursing on the whole list, use 2 iterators (nested loops).

• Using two iterators above, I input a list 20,000 integers backwards and bubble sorted it in 963 seconds. On my machine, the time increased by a factor of 4 for each doubling in list length. This is worst case only. Nov 4, 2019 at 4:09