Bubble Sort
**DISCLAIMER: This code is in C++, but the logic applies to other languages**
1) What is bubble sort?
Bubble sort is a sorting algorithm that checks adjacent numbers and swaps them if the number being checked is larger than the number ahead of it. The numbers are ordered from the bottom (end) of the list to the top (beginning). Kinda reminds me of the way bubbles rise to the surface of water *gasp!*
Visual Example:
2) An example problem:
- Sort the numbers in the array [23, 123, 234, 54, 44, 2, 1432, 123, 8, 0].
- Create a bubble sorting algorithm to order the numbers from least to greatest.
3) How I attempted to solve it:
- I knew I needed to make a for-loop to iterate through the array.
- I knew I also needed an if-statement to check if the indexed number was larger than the indexed number adjacent to the right of it.
- My code logic* looked like this:
4) What happened?
- This is what I got: [23, 123, 54, 44, 2, 234, 123, 8, 0, 1432, ]
- So it seems like 1432 is in the correct position (based on the definition of bubble sort), but everything else seems to be off. I couldn’t figure out what was wrong.
5) What I ended up realizing:
- After writing and rewriting the list and solving the sorting by hand 100 times, I realized I hadn’t even been following the structure of my own logic.
- Once the if statement is complete, the loop iterates to the next index in the array. Therefore the number at index 0 of the array will always stay at the position. Hmm, if only there was a way to reset the loop to index 0 and run it again and again until the list was sorted…………….
6) THE FIX!!
- There is! Another loop! I created an outer for-loop. The code now looks like this:
(I took this screenshot w/ more white space on the right so it looks better. The first screenshot is really in your face. Don’t worry, I know.)
- I printed all the numbers returned after every iteration. This is the result:
- [23, 123, 54, 44, 2, 234, 123, 8, 0, 1432]
- [23, 54, 44, 2, 123, 123, 8, 0, 234, 1432]
- [23, 44, 2, 54, 123, 8, 0, 123, 234, 1432]
- [23, 2, 44, 54, 8, 0, 123, 123, 234, 1432]
- [2, 23, 44, 8, 0, 54, 123, 123, 234, 1432]
- [2, 23, 8, 0, 44, 54, 123, 123, 234, 1432]
- [2, 8, 0, 23, 44, 54, 123, 123, 234, 1432]
- [2, 0, 8, 23, 44, 54, 123, 123, 234, 1432]
- [0, 2, 8, 23, 44, 54, 123, 123, 234, 1432]
(I took out the end comma, added brackets, and numerically listed them to make it easy for y’all to read so don’t @ me. :D )
Hope this helped! Thanks for reading :)
7) Summary and run-time:
- Iterate through the array (inner for-loop).
- Check to see if the current number is greater than the one on its right (if-statement inside inner for-loop).
- Restart the for-loop over and over again until the list is sorted (outer for-loop).
- Run times:
- Worst Case: O(n^2)
- Best Case: O(n)
- Average Case: O(n^2)
*I wrote this code, but this isn’t the problem I was assigned. I wrote this code replaying my thought process in figuring out the solution. That is why this is an example problem.
*Also, I make lots of mistakes. There may very well be mistakes in my code even though it produces the correct output. Kindly correct me so misinformation isn’t spread. Thanks! :)
