Skip to content

Instantly share code, notes, and snippets.

@jootse84
Last active September 19, 2018 23:25
Show Gist options
  • Save jootse84/3c51a776471a37beebac10d42ba9f42f to your computer and use it in GitHub Desktop.
Save jootse84/3c51a776471a37beebac10d42ba9f42f to your computer and use it in GitHub Desktop.
Bubble sort recursive implementation in Python
def bubble(l_elems, is_sorted, step):
if step is 1 or is_sorted:
# base case: l_elems is already sorted or we pass through the list len(l_elems) times
return l_elems
else:
is_swapped = False
for i in range(len(l_elems) - 1):
# compares each pair of adjacent items and swaps them if they are in the wrong order
if l_elems[i] > l_elems[i + 1]:
is_swapped = True
l_elems[i], l_elems[i + 1] = l_elems[i + 1], l_elems[i]
# if is_swapped is True, the algorithm needs to pass through the list again
return bubble(l_elems, not is_swapped, step - 1)
print(bubble(range(10,0,-1), False, len(range(10,0,-1))))
print(bubble([5,6,5,3,3], False, len([5,6,5,3,3])))
@PaulMorris
Copy link

Nice recursive implementation! I understand the code and it's not hard to follow. Comments are clear and helpful.
Running it in a console produces correct results for test cases, and as far as I can see any possible cases... I tried it with an empty array and it worked fine. My only suggestions are two very minor nits:

  1. "l_elems" is kind of harder to read with the underscore, maybe just use "elems" ?
  2. Maybe have two functions, a recursive inner function and an outer wrapper function that only takes an array, that way you don't have to supply "False" and the length of the array to the outer function, since those are defaults or can be determined from just the array.

@jootse84
Copy link
Author

@PaulMorris thanks for the comments they are very helpful!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment