Bubble Sort Algorithm
Bubble sort is a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Bubble sort uses nested loops.
Because of the nested loops, bubble sort has a runtime of O(N2). Bubble sort is very intuitive and easy to wrap your head around and is often considered impractical for real-world use because many faster sorting algorithms exist. However, it’s an important algorithm to understand because it teaches you about complexity analysis and prepares for tougher more optimal sorting algorithms like merge sort and quicksort.
Let’s dive into the explanation of how it works.
Our goal is to sort a list of numbers in ascending order. We are going to iterate through a list, compare each number to the next number, and perform swaps if they are out of order. Computer scientists call it a bubble sort because the numbers with the highest values “bubble up” to the end of the list, and the numbers with the smallest values move to the beginning of the list.
Given a list with N elements, the first time we iterate, we are going to traverse through it from the start to the end, and at each number, we are going to check if these two numbers are in the correct order — if the current number is smaller than or equal to the next number. If they are, we keep moving to the next item in the list, and if they are not in the correct order, then we swap them in place and continue moving to the next number. Once we finish traversing the list once and we get to the end, we redo our entire iteration once again to see if any items are out of order. If the array is fully sorted then we are done and we return the array. It’s important to know that bubble sort happens in place. When we swap two numbers, we are doing it in place, we are not using any additional space (like a helper list). This differentiates bubble sort from merge sort, for example.
Let’s now look at a simple example.
[32, 1, 9, 6, 20]
is 32 <= 1?
No, we swap 32 and 1
[1, 32, 9, 6, 20]
We move on to the next index
Is 32 <= 9?
No, we swap 32 and 9
[1, 9, 32, 6, 20]
Is 32 <= 6 ?
No, we swap 32 and 6
[1, 9, 6, 32, 20]
Is 32 <= 20 ?
No, we swap 32 and 20
This is what our list looks like after the first iteration:
[1, 9, 6, 20, 32]
The last item is in the correct spot. Now we can iterate a list from index 0 to 3.
At the second iteration, we start our checks at index 0 again and continue checking and swapping up to index 3 (32 is already sorted).
[1, 9, 6, 20, 32]
At the end of our second iteration, our list looks like this:
[1, 6, 9, 20, 32]
We continue comparing adjacent elements until we reach the end of the list, and we are done. The list is fully sorted.
Now let’s look at one version of the bubble sort implementation in Python.
def bubble_sort(arr):
# loop to access each array element
for i in range(len(arr)):
# loop to compare array elements
# start at idx 4, end at 0, go one step from end to start
for j in range(len(arr)-1, i, -1):
# compare two adjacent elements
if arr[j - 1] > arr[j]:
# swap elements if not in the intended order
(arr[j - 1], arr[j]) = (arr[j], arr[j - 1]) return arr
Your algorithm’s comparisons all happen inside your inner loop where we do comparisons and swaps in the reverse order. Your outer loop is there only to keep your algorithm running for as many swaps as it takes to put your list in order.
After one iteration, the smallest number moves to the front of your list, so you no longer have to compare numbers to it because you know it’s the smallest item in your list. The second time through your inner loop, the second-smallest value will move to its final position, second from the start. Each time through your inner loop, your inner loop can terminate sooner.
A bubble sort’s main advantage is how simple it is to implement, making it a good starting point with sorting algorithms. Because a bubble sort relies on two nested loops, its time complexity is O(n^2), which means while it can be acceptable for small sets of data, it’s not an efficient approach for sorting large data sets.
Explore other common sorting algorithms:
