Did you all dance to that title? Because I sure did.
Ok, so what is bubble sort?
It’s a comparison-based algorithm that compares each pair of items that are next to each other in a list and swaps them if they are in the wrong order. The name “Bubble” comes from how the larger items “bubble” to the top of the list during each iteration. It keeps going until no more swaps are needed.
No worries...let's break it down.
Let’s say we have an array of items: [10, 5, 11, 20, 1]
First, bubble sort is going to compare 10 and 5 since they are the two elements. Since 10 < 5, we are going to swap their places. So now, our list will look like this:
[5, 10, 11, 20, 1]
See how the 5 is now before the 10 and is technically in “order”?
Now let’s go through the rest! We’ll compare 10 to 11. Since 11 > 10, there’s no need to swap.
You get the gist! You is smart.
So once we go through the rest (11 compared to 20 and 20 compared to 1), we arrive at the end of the first round:
[5, 10, 11, 1, 20]
Wait a minute, Rue. That’s not in order!
That’s right – we aren’t done! Remember what I said about how bubble sort will keep going until no more swaps are needed. 1 needs to move up. So we do another pass, and another, aaannnnddd another. This is what our list will look like after each pass:
1. [5, 10, 11, 1, 20] (the one from above)
2. [5, 10, 1, 11, 20]
3. [5, 1, 10, 11, 20]
4. [1, 5, 10, 11, 20]
Wow talk about a long walk for a short glass of water. See, bubble sort isn’t efficient when it comes to big list. Imagine running this code when you have 1000’s of items in an array. You might break the interviewer’s computer and then you have to do a shameful scurry out of the room. Then you bump into them at a Starbucks and avoid eye contact. It’s no bueno.
In proper terms, it has a worst-case and average time complexity of O(n^2).
I’ll be making a post soon about how this would look if we wrote out some code and even do some…TESTING (LE GASP!).
-Rue