In this installment of SwiftyAlgos I am taking a look at Bubble Sort. Bubble Sort is largely considered to be one of the simplest of sorting algorithms. It works on the principal of iterative swapping, working programmatically through a collection and swapping value positions until ultimately reaching a point where all of the values are in the correct order.
It works like this…
simple put, we loop through each pair of indices, and compare the values, if the left is greater than the right we swap, if not we do nothing. Once we are able to loop through and have no swaps we can assume that the collection is sorted. Ideally this is best for small collections, even this simple example requires 3 total passes of 4 comparisons each; effective but not performant.
Let’s take a look at this in code…
and test it…
Check out the code here on GitHub
Closing thoughts…
Bubble sort is simple, which in some ways makes it rather elegant in my opinion. But elegant isn’t alway great, in the case of bubble sort it’s very time consuming, effective, but time consuming. This algorithm demonstrates a couple of great things, the first in fact being the reality that the dumbest possible solution is often a great place to start, especially when looking at the potential complexity of sorting collections. It also demonstrates how effective loops can be at tracking position for controlled outcomes. Thanks again to GeeksForGeeks for providing a great resource for learning CS concepts, and thanks also to a great new resource that I found on GitHub, The Swift Algorithm Club! As usual it’s important to remember that when you explain an idea you take the greatest steps towards mastery.
Until next time!
Dining With Robots 