BubbleSort uses nested for loops in order to sort an array and therefore has a time complexity of O(n^2). That is slow, but it is still an important algorithm to know.
How it works:
Take array, arr = [54, 26, 93, 17, 77, 31, 44, 55, 20] size, n = 9
BubbleSort compares two adjacent elements and the larger value is put to the right/bigger index.
eg: arr[0] = 54 and arr[1] = 26 since arr[0] > arr[1] we will put the larger value to the right or bigger index i.e.: arr[1] = 54 and arr[0] = 26
If we use the above logic and iterate through the entire array once, we will have the largest value in the array placed at the end:
Now, that we have the largest element at the end we can ignore the last element of the array and apply the same logic to arr n-1, n-2, n-3, ..., 1, 0; This can be achieved using the nested/outer for loop on the array.
Algorithm:
def bubbleSort(arr):
# variable i will be used to decrease the array iterated through
# by the inner for loop by size 1 (n-1, n-2, n-3 ... 0);
# since after each iteration of the inner for loop the largest element is at the last index
# and thereby in the correct sorted index.
for i in range(len(arr)):
# len(arr)-i = 9 (9-0), 8(9-1), 7(9-2), ... 0 (9-9)
# The -1 value is used since we will be comparing i with i+1 and that
# could lead to index out of range error
for i in range((len(arr)-i)-1):
# check if smaller index i is larger than bigger index i+1
if arr[i] > arr[i+1]:
# save arr[i] value in temp, overwrite arr[i+1] value to arr[i] and then replace arr[i+1] with larger temp/arr[i] value
temp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = temp
return arr
print(bubbleSort([54, 26, 93, 17, 77, 31, 44, 55, 20]))