Bubble Sort
code: python
# O(n^2), O(1)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# print("=====")
for j in range(n-1, i, -1):
# print(j-1, j)
return arr
def test_bubble_sort():
assert bubble_sort(5, 9, 3, 1, 2, 8, 4, 7, 6) == 1, 2, 3, 4, 5, 6, 7, 8, 9 # =====
# 7 8
# 6 7
# 5 6
# 4 5
# 3 4
# 2 3
# 1 2
# 0 1
# =====
# 7 8
# 6 7
# 5 6
# 4 5
# 3 4
# 2 3
# 1 2
# =====
# 7 8
# 6 7
# 5 6
# 4 5
# 3 4
# 2 3
# =====
# 7 8
# 6 7
# 5 6
# 4 5
# 3 4
# =====
# 7 8
# 6 7
# 5 6
# 4 5
# =====
# 7 8
# 6 7
# 5 6
# =====
# 7 8
# 6 7
# =====
# 7 8
# =====