Last active
September 19, 2018 23:25
-
-
Save jootse84/3c51a776471a37beebac10d42ba9f42f to your computer and use it in GitHub Desktop.
Bubble sort recursive implementation in Python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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: