Bubble sort
Best Case, O(n)
Worst Case, Ω(n^2)
Memory Complexity, O(1)
#!/usr/bin/python
import random
def bubble_sort(l):
n = len(l)
for i in range(n):
for j in range(n-i-1):
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
def get_list():
random.seed()
l = random.choices(range(10), k=10)
return l
def main():
l = get_list()
print(l)
bubble_sort(l)
print(l)
if __name__ == '__main__':
main()
Reach Best Case with Control
#!/usr/bin/python
import random
def bubble_sort(l):
n = len(l)
for i in range(n):
swap = False
for j in range(n-i-1):
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
swap = True
if not swap:
break
def get_list():
random.seed()
l = random.choices(range(10), k=10)
return l
def main():
l = get_list()
print(l)
bubble_sort(l)
print(l)
if __name__ == '__main__':
main()
Reference