BubbleSort
Description
Repeatedly swap adjacent elements if they are in the wrong order. The first traversal should bubble the largest element to the end. Then the second traversal should bubble the 2nd largest element to the second last index and so onwards.
Complexity Analysis
Average case | \( O(n^2) \) |
|---|---|
Best case | \( O(n) \) |
Worst case | \( O(n^2) \) |
Space Complexity | \( O(1) \) |
def bubbleSort(arr):
for i in range(len(arr)):
# Assumes largest ith numbers are already placed at the end of the array, hence no need to iterate over them
for j in range(len(arr) - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arrGeoffrey Lee