Ahh Sorting Algorithms...
Such a simple problem, yet so hard to do quickly... let me rephrase that, such a simple problem, yet so hard to do quickly given large quantities of things that need sorting. There are simple solutions to this problem, and then there are complex ones, but you are going to learn about the simpliest of all sorting algorithms, Bubble Sort.
The Bubble Sort algorithm is always an interesting (sometimes painful) topic of discussion. You have some people who are new to programming, algorithms, and data structures and have no idea what Bubble Sort is, some who believe that Bubble Sort is "an abomination to the computer programming world and should never be used in any situation, so help me God!"...and then there is everyone inbetween. Whichever area of that spectrum you find yourself residing in, I welcome you to my breif discussion of this fascinating and fascinatingly simple sorting method.
So for you newcomers, what is Bubble Sort? Bubble Sort is one of the oldest and simpliest algorithms for sorting a given set of information. In this algorithm, you compare two adjacent values in an array, if the second value is less than the first, you flip the positions of the two values. In essence, the small values will "bubble" their way to the top/front of the array, and the larger values will "sink". Do you remember in 3rd/4th grade science class when the teacher took a bunch of different liquids of varrying viscosities, put them in a container, and then shook it up? Bubble Sort works just like that. The lighter values/liquids float to the top while the heavier values/liquids sink. This process of comparing and flipping values will continue in the Bubble Sort algorithm until you have a nicely sorted list.
Sounds great, right? Well there is a reason there is a group of people that hate it more than Windows ME. Bubble Sort is the worst performing sorting algorithm, by far. I won't go into details about time complexities, but in case you are ever asked this question in Team Trivia, Bubble Sort has a time complexity of O(n^2). That is bad. When you think about what Bubble Sort is doing, like previously discussed, it is fairly easy to see why this isn't the best way to sort a list. But before you shun Bubble Sort completey, this algorithm does have some great uses, but first, lets look at this beast of an example program:
Boom, there she is. A whopping eight lines of beauty. If you are new to programming, this may seem foreign to you, so I will give you a breif rundown. The arrayToSort array is pretty straightforward in what that is and the temporaryInt variable is what we use to hold one of the values that will be swtiched when needed. The outer for loop keeps track of how many times the program has looped through the data. In this implementation of Bubble Sort, the number of times we loop through the data will always be the length of the array we are sorting - 1 (given this many iterations, we know the array will be sorted...Why? Well, just trust me on that). The inner for loop is where we iterate through the array we want sorted, starting at index 0 (first value in array), all the way to the second to last value. This loop goes to the second to last value because if went to the last value, then when we compare the last value to the next value...well there is no next value, right? Right. That is why we do that. Inside the inner for loop, we have where all the true work is done for Bubble Sort. The if statement says that if the value at index i is less than the value at index i + 1, we switch them. This is where the temporaryInt variable comes into play and it is easy to see why this is needed. In the programs given state, there is no output, but if there were, it would look something like this:
What a good looking list! So, that begs the question, when would you use this besides in your first undergrad data structures or algorithms class? The beauty of this sorting algorithm is that is simple, short, and incredibly easy to implement. I can write a Bubble Sort program in ten seconds with my eyes closed. One situationI have used Bubble Sort extensively is in testing segments of larger programs. Rather than spend a large amount of time getting a more complex sorting algorithm to work with my data, I code up Bubble Sort quickly and continue working on more pertinent sections of a program. This allows me to build prototypes and test code segments quicker. When I get the program working, I go back and change it to a quicker sorting algorithm. Since the output of a sorting algorithm is always the same, given it works correctly, it really doesn't matter if it is fast to start with. Similar to the saying, "Rome wasn't build in a day", it can be very benefitial to start simply, sacrifice efficiency, and after you get your program working, polish it off with more efficient sorting algorithms. Trust me, this can save you many headaches, especially when working on large projects.
Besides that, Bubble Sort can also be beneficial in situations where you know you will always have a small number of elements to sort, or where you know the elements will always be almost sorted. A faster sorting algorithm may still be faster in these situation, but it is rather pointless to implement them when given that information. It either won't be worth the program space, programmer time, or you would never notice the time difference. Think about it this way...if you lived a block away from the store, would you buy a Ferrari just to make your drive there shorter? No, you wouldn't (the normal person wouldn't anyway). Even though your Honda Civic is significantly slower than a Ferrari, it just wouldn't be worth the investment...and let's be honest, you wouldn't really notice a time difference either.
There can be a lot of beauty in simply things, and Bubble Sort is no exception. I have been programming for years, and still find many situations where Bubble Sort can be beneficial. Even though it isn't the most efficient sorting algorithm there is, it is still important to understand it and know how you can apply it.
If you have made it this far, thank you. This is my first article of many to come. Topics include, algorithms, machine learning, computer vision, and the like. I appreciate all feedback and I always love have great conversations with new people.
