Double Bubble Sorting and Trouble
If Macbeth were a programmer, he would work with data all day every day. Big data, small data all types of data. Working with all this information can be quite unruly at times, which is why theres nothing like a good sorting algorithm to get all that data in order. There are many, many sorting algorithms. Selection, insertion, merge and so on, but for the breadth of this article I’ll be focusing on our friend bubble sort. Let’s dive in!
The Gist
We all know what sorting is, but let’s define it just to be thorough. When we sort we are going through the process of rearranging the items in a collection (an array) so that the items are in some sort of order. Smallest to largest, alphabetical, date, etc.
At this point you may be thinking to yourself, “Hold the phone, JavaScript has a built in sort method, why not just use that?” Why not indeed…
JavaScript has a built in method, .sort(), which looks at a pair of elements (a and b) and determines their sort order based on the value of a - b. If a minus b results in a negative (-) number being returned, then a comes before b. If a minus b results in a positive (+) number being returned, then b comes before a. If 0 is returned, then a and b are the same.
Great, so what’s the problem? Well, funny you should ask. If we use the .sort() method on an array of strings it will sort them alphabetically. If we try to sort an array of numbers however there doesn’t appear to be any discernible pattern. If we take a deeper dive and take a look at the JavaScript documentation on MDN in regards to the .sort() method we find that the default sort order is “according to string Unicode code points.” What this means is that JavaScript converts each element into a string and then the value is taken from that and then sorted. This leads to unexpected behavior which is not what we want.
Rise to the Top
Let’s take a look at one sorting algorithm that is called ‘bubble sort’. It is called this because the largest values will bubble to the top. What this algorithm will do is loop through each item in the array and as we loop we will compare the current item to the next item in the array. Then we check to see if the current item is larger than the one we are comparing it to, if it is larger, we swap.
Let’s walk through an example array:
let exampleArray = [5, 3, 4, 1, 2]
- Compare 5 and 3
- Swap, [3,5,4,1,2]
- Compare 5 and 4
- Swap [3,4,5,1,2]
- Compare 5 and 1
- Swap [3,4,1,5,2]
- Compare 5 and 2
- Swap [3,4,1,2,5]
- That is one iteration, we need to repeat the process to sort the rest of the array.
Many sorting algorithms have some sort of swapping functionality, but how do we swap these elements?
Pseudo Bubble Sort
- Write a function that takes in an array of numbers.
- Start looping with variable i from the end of the array towards the beginning
- Start an inner loop with variable j from the beginning until i -1
- If arr[j] is greater than arr[j + 1], swap those two values
- Note: we want to shrink the number of comparisons that we are making because we are sorting the array as we go therefore there will be less comparisons that we need to make
- Because we are dealing with nested loops we know right off the bat that we are going to be dealing with a Big O of n².
The Real Bubble Sort
As they say in the terminal, “Happy Hacking!”
