Implement bubble sort in Python

Question

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)

• Gareth Rees: Bubble sort can't be optimized!

Answer 1

thanks for sharing your code.

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.

2. 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)

A few additional things,

• 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!

Answer 2

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).

• James Kelley: 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.