Students and interested readers are probably dabbling in writing algorithms right now and have heard of the Bubble sort. A simple sorting algorithm that your program can run that will sort whatever data you feed inside of it.
That all sounds fantastic, so how can we do it? Well, while a bubble sort is known to sort the data you give it, it comes at a cost. The bubble sort ends up being a very slow (computationally) algorithm.
In computer science, we focus on something called asymptotic time. Asymptotic time is how much we measure the time it takes for our algorithms to complete the operations you instructed.
Usually, we will only concern ourselves about asymptotic time, when the number of data that we have is very large. Here’s why, lets imagine we have 5 numbers: 5, 9, 6, 2, 3 and we want to sort these numbers.
In the Bubble sort algorithm, we start at the very beginning of our list, moving to the next element step by step. As we move to the next element, we are comparing the value of the element we stepped on and the element that’s on the next step. In our example, we look at 5 and compare 5 with 9.
If the next steps’ value is smaller than our current step, we switch their places. We continue doing this process for every element in the list. The first time we did the switching of places, we went through the list 5 times. N = 5. Even so, we might have not swapped EVERY element so that they would be in the correct position of the list. Let’s go through the N=5 steps just mentioned.
1st time: 5, 9, 6, 2, 3
Is the next value smaller than the current one?
5 > 9 = False (no-swap)
9 > 6 = True (Swap)
9 > 2 = True (Swap)
9 > 3 = True (Swap)
The list currently (notice our list is still not sorted):
5, 6, 2, 3, 9
We would have to continue going through the checks of each element in our list until our list is finally sorted. As you can see, it can take going through the list if it was reverse sorted, the maximum number of times it needs to pass through.
That’s an issue, just imagine if you had thousands or millions of numbers in a list and you had to wait an n2 number of times for the list to complete sort. Would you like to use Google if you had to wait a long time for your search to be found?
The Worst-Case and the Best Case of Bubble Sort
Our discussion of asymptotic time leaves us to discover the worst case and best case of the Bubble sort. I’ll summarize it.
The worst-case tells us what is the worst possible circumstance that our algorithm will perform slowly. As we mentioned before if the list is reverse sorted, it could take our algorithm the max number of times to pass through. That’s denoted in the commonly used O(n2).
The best-case tells us what is the best possible circumstance that our algorithm will perform quickly. That case will come if the list is already sorted, but not reverse sorted. This would only take the algorithm O(n) or n times to pass through.
A Quick Implementation
To implement a bubble sort we’ll use python, I will inline comment what is going on throughout the code:
def bubbleSort(arrOfNumbers): n = len(arrOfNumbers) # Get the length of the entire array. for i in range(n): # The first loop travels through the list. for j in range(0, n-1): # The second loop travels through the list from 0 to n - 1 checking all numbers in list. if arrOfNumbers[j] > arrOfNumbers[j+1]: # If the number is greater we continue to move it to the front of the list. # We're using temp to show you that we're temporarily # holding the old value and swapping with new value (j+1). temp = arrOfNumbers[j] arrOfNumbers[j] = arrOfNumbers[j+1] arrOfNumbers[j+1] = temp # We complete the swap. arr = [1,2,3,6,1,62,3,51,1] bubbleSort(arr) for i in arr: print(i)
If you’re interested in reading about other data structures click this link here