Data Structures and Algorithms 101 : The Bubble Sort
As I continue on my job search and my studies of data structures and algorithms (DS&A), I thought it would be helpful to discuss one of the simplest and fundamental algorithms in DS&A, the bubble sort. The bubble sort, as you can tell from its name, is a sorting algorithm which compares each pair of adjacent elements and swaps them if they are not in order. It is important to note that the bubble sort algorithm is not the most efficient algorithm when tackling large data sets because its worst case and average case time complexity is O(n²) where n is the number of items. (If you are not familiar with time complexity, check out this resource here)
How Does The Bubble Sort Work?
Let’s look at an example of the bubble sort so that we can see how it works! Imagine we are given the array [23,15,5,20,75,14] and we are asked to sort it in ascending order. We can use the bubble sort algorithm to sort the array! As I stated earlier, the bubble sort compares the values of two adjacent elements and then swaps their values if the first value is greater than the second. This will allow the larger numbers to “bubble” up to the top and with each pass through the array, the last element will be in the correct order. So if we look at the first pair of values in the array, 23 and 15, since 23 is greater than 15, we swap the values and move on to compare the next pair of values, 23 and 5. This process will continue until the array is sorted.
Iteration 1: [23,15,5,20,75,14] → [15, 23, 5, 20, 75, 14] → [15, 5, 23, 20, 75, 14] → [15, 5, 20, 23, 75, 14] → [15, 5, 20, 23, 75, 14] → [15, 5, 20, 23, 14, 75]
Iteration 2: [15, 5, 20, 23, 14, 75] → [5, 15, 20, 23, 14, 75] → [5, 15, 20, 23, 14, 75] → [5, 15, 20, 23, 14, 75] → [5, 15, 20, 14, 23, 75] → [5, 15, 20, 14, 23, 75]
Iteration 3: [5, 15, 20, 14, 23, 75] → [5, 15, 20, 14, 23, 75] → [5, 15, 20, 14, 23, 75] → [5, 15, 14, 20, 23, 75] → [5, 15, 14, 20, 23, 75] →[5, 15, 14, 20, 23, 75]
Iteration 4: [5, 15, 14, 20, 23, 75] → [5, 15, 14, 20, 23, 75] → [5, 14, 15, 20, 23, 75] →[5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75]
Iteration 5: [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75] → [5, 14, 15, 20, 23, 75]
As you can see from the iterations above, it took 5 iterations to complete the sort for the array that was given. You will also notice that after iteration 4, the array was sorted, however, the bubble sort iterates through the array one last time to make sure no other swaps are necessary before returning the sorted array.
Now lets look at one way to code the bubble sort function. (coded in JavaScript)
The function above will run until the variable i and j are equal to the length of the array, which means that it may run on an already sorted array more than once. A simple way of thinking about this is for each element that the function iterates through, the function will iterate through the array again for every element in the array. This is why we see a time complexity of O(n²) where the number or iterations is based on the number of elements, squared.
Conclusion
Well, I hope this little walk-through and explanation helped you understand bubble sorting a little better. The truth is, it is not commonly used since it is not very efficient. None the less, it is an important algorithm to understand because its fundamentals are the foundation of many other algorithms. If you have any additional questions, I urge you to keep researching and practicing. Thanks for reading and I’ll see you next week!