from datetime import datetime
# Time Complexity O(n^2)
# Space Complexity O(1)
# neighbours change places until a pass makes no swaps:
# the largest element "bubbles up" to the end on every pass
def bubble_sort(data):
lst = list(data)
for end in range(len(lst), 1, -1):
swapped = False
for j in range(1, end):
if lst[j] < lst[j - 1]:
lst[j], lst[j - 1] = lst[j - 1], lst[j]
swapped = True
if not swapped:
break
return lst
items = [4, 1, 5, 3, 2]
sort_items = bubble_sort(items)
# sort_items is [1, 2, 3, 4, 5]
print(items)
print(sort_items)
# *** simplified speed test ***
items = list(range(199, 0, -1))
count = 1000
start = datetime.now()
for n in range(1, count):
bubble_sort(items)
delta = datetime.now() - start
total_milliseconds = delta.seconds*1000 + delta.microseconds//1000
print(f"{total_milliseconds} milliseconds")
# about 752 milliseconds