One of the most daunting things I find about coding tech interviews is the heavy emphasis on Data Structures and Algorithms. Perhaps it’s because I’m coming from a bootcamp background, and it wasn’t heavily touched upon — but no matter who I speak to (computer science degree holders or not), it’s a heavily tested subject and a must know for interviews.
As such, I’ll be covering the five most popular sorting algorithms in this five part mini series. Today, I’ll be reviewing bubble sort, with selection, insertion, merge and quick sort to be covered in subsequent posts.
If you’re ready, let’s jump right in!
Bubble Sort: How It Works
Bubble sort is the simplest sorting algorithm. It works by comparing adjacent elements and swapping them if they are in the wrong order.
list = [ 4, 7, 1, 6, 10, 8, 3, 9, 7, 5, 2 ]Let’s take the list above, for example. The goal is to sort this list from ascending order. So, in the above case, from 1 all the way to 10.
In the first iteration, Bubble Sort starts off with the first element in the list (4, in this case), which is compared to the second element (7). If the first element is greater than the second, the two swap places. If the first element, is not bigger than the second number, nothing occurs, and we move onto the next two elements in the list (7 and 1).
Since 7 is greater than 1, the two numbers swap places — and again, we move onto the next two elements (7 and 6). As 7 is greater than 6, the two number switch places, and we move on to the next two elements (7 and 10). Since 7 is not greater than 10, no swap occurs, and we move onto 10 and 8. This process continues until we reach the end of the list where 10 and 2 swap places, resulting in the list below:
list = [ 4, 1, 6, 7, 8, 3, 9, 7, 5, 2, 10 ]As you can see, 10 is the highest number in the list and is in the correct spot, but the rest of the list is still out of order. So, we’ll iterate through the list again, repeating the cycle.
Moving on to the second iteration, we start off with 4 and repeat the process above. By the end of the second iteration, we get the following list below:
list = [ 1, 4, 6, 7, 3, 8, 7, 5, 2, 9, 10 ]Now, 9 and 10 are in the correct place, but a few numbers still remain out of order. To solve this, we’ll need to perform n iterations on this list n times to get everything sorted (* n referring to the number of elements in the list).
Ultimately, the sorting algorithm stops when no more swaps occur, meaning all the elements are in its correct place, and the list is finally sorted in ascending order.
list = [ 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10 ]Time Complexity
As we need to iterate through the list n times to complete the sort, bubble sort has a time complexity or big O notation of O(n2).
Why O(n2)?
In the example above, we have n = 11 elements. As we run through the length of the array, we iterated through n (11) elements, the first time. We then iterated over the list again and again. Theoretically, for a fully unsorted list, we iterate through every element in the list (n), for the size of the list (n), leading to a time complexity of (n x n), or (n2).
Algorithm
Now that we have the theory out of the way, let’s build our very own bubble sort algorithm! * The code below is written in Python, but the general logic should be the same in whatever language you choose.
Let’s keep it simple by first selecting and comparing the first two numbers in the list: arr[0] > arr[1] .
We aren’t just dealing with the first two numbers though, so let’s add a for-loop to have it iterate down the array.
for num in range (len(arr) - 1):
arr[num] > arr[num + 1]Keep in mind, we’re using len(arr) - 1 because we don’t need to loop through the last number as there will be no second number for it to compare to!
To perform the actual swap now, we can reassign both values dynamically: arr[num], arr[num + 1] = arr[num + 1], arr[num]
As we only want the swap to take place if arr[num] > arr[num + 1], we’ll throw in an if-statement:
for num in range (len(arr) - 1):
if arr[num] > arr[num + 1]:
arr[num], arr[num + 1] = arr[num + 1], arr[num]This isn’t quite it though. The above code will only cover the first iteration of the list. So, how do get to iterate it through n times?
One way is to run a loop for the number of elements in the list. For example, using the list at the beginning of the article, we run the above code 11 times. This isn’t very efficient code though, because if you end up with a sorted list by the forth or fifth iteration, the loop will nonetheless continue, making it inefficient.
Another way to implement this is to incorporate a status tracker with the help of booleans. When the status tracker is True, we enter a while-loop, where we reset the status tracker to False(to prevent an infinite while-loop), and then enter a for-loop.
The for-loop will continue to run through the length of the array (minus 1), until a number is greater than another. When this happens, a swap finally occurs. We then reset the status tracker to True, break out of the for-loop, and restart the while-loop.
On the final iteration, when the list is fully sorted, and no swapping occurs, the status tracker will never be reset to True, thereby, breaking out of the while-loop and ending the sorting algorithm.
I know — that’s a lot of wording, but the code below summarizes it all:
def bubble_sort(arr):
swap_happened = True
while swap_happened:
swap_happened = False
for num in range(len(arr) - 1):
if arr[num] > arr[num + 1]:
arr[num], arr[num + 1] = arr[num + 1], arr[num]
swap_happened = TrueAnd, that’s it! Hopefully, this bubble sort tutorial gave you a good foundation to start with. If you’re still having doubts, it’s best to just get some practice in. My best advice is to check out practice problems on Leet Code and go from there.
Be sure to stay tuned for the next topic in the series: Selection Sort! See you soon. Thanks for reading!
