With a worst case complexity of O(n^2), the Bubble Sort is the front door of the sorting algorithms.
The algorithm loops through the array, comparing an item on the i position with the item on the i+1 position.
In other words, the current item is compared to the one right after it.
If the current item is greater than the next one, their positions are swapped.
Consider the array below.
[32, 17, 23, 5]
Applying the Bubble Sort, the bold and italic items are the ones being compared.
If the item on the left is greater than the item on the right, we have an Exchange, otherwise, it stays the same.
When 32 reaches its position, we do the same process with 17 and keep going until all items go through the process.
Notice that we no longer compare the last element after the first pass of the algorithm since it is guaranteed it will be the biggest item.
| 32 | 17 | 23 | 5 | -> Exchange
| 17 | 32 | 23 | 5 | -> Exchange
| 17 | 23 | 32 | 5 | -> Exchange
| 17 | 23 | 5 | 32 | -> No Exchange
| 17 | 23 | 5 | 32 | -> Exchange
| 17 | 5 | 23 | 32 | -> Exchange
| 5 | 17 | 23 | 32 |
Another way to look at it is that, at each pass, we will have the last item in place (the biggest), then the second to last (the second biggest), and so forth.
This way we can save computational power by avoiding unnecessary comparisons on the later rounds.
Implementation
The algorithm starts by calculating the number of items to loop through.
Since the array index starts at zero, we subtract one, this way, for 4 items, for instance, the loop goes from 0 to 3 instead of 0 to 4.
The first loop goes from 0 until the number of items.
The second loop will make the comparison of the j item with the j+1 item.
Notice how the second loop goes until num_items-i, meaning that, after each pass of the algorithm, we won’t compare the items already in place.
Since i starts with 0, the second loop compares all items in the first pass.
For i equals to 1, the second pass, the second loop goes only until n-1, so the last item is skipped.
For i equals to 2, the third pass, the second loop goes only until n-2, so the last two items are skipped.
This continues until i is equals to num_items and the algorithm ends.
def bubble_sort(arr):
num_items = len(arr)-1
for i in range(num_items):
for j in range(num_items-i):
if arr[j]>arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [32, 17, 23, 5]
bubble_sort(arr)
print(arr)The output will be:
[5, 17, 23, 32]To see the algorithm in action for each item in the list, insert a print() right after the second for loop.
Then, insert a second print() after the if block to see the current state of the array at each iteration.
def bubble_sort(arr):
num_items = len(arr)-1
for i in range(num_items):
for j in range(num_items-i):
print(f'{arr[j]} <-> {arr[j+1]}')
if arr[j]>arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)
arr = [32, 17, 23, 5]
bubble_sort(arr)
print(arr)The output will show the pairs being compared and exchanged until the we have the final sorted array.
32 <-> 17
[17, 32, 23, 5]
32 <-> 23
[17, 23, 32, 5]
32 <-> 5
[17, 23, 5, 32]
17 <-> 23
[17, 23, 5, 32]
23 <-> 5
[17, 5, 23, 32]
17 <-> 5
[5, 17, 23, 32]
[5, 17, 23, 32]