There are some algorithms that are famous,
and some that are infamous. One of the latter is the often maligned Bubble Sort. So, what is the bubble sort? Why is it infamous? How do we code it?
First of all, lets talk about sorting algorithms in general and the problems of scale. Sorting algrorithms are popular subjects for beginning and intermediate computer science courses. They provide an ideal platform to introduce concepts like worst case execution time or storage (big O notation), different data structures and there are lot and lots of them to play with and see firsthand the differences. So, being a student of computer science myself I thought I would share this one. It is simple, and it demonstrates how we can tie up resources pretty quickly if we aren’t careful. The inefficiency of the Bubble Sort is what makes it so infamous by the way. I’m told even president Obama when being questioned by the CEO of google as to how he would sort a million integers responded with “Well, I wouldn’t use a bubble sort” or something thereabouts. Infamous.
Let’s look at a random numerical list:
n = [1,5,8,2,10,11,4,3,9,7,34,56,23,46,6]
Now lets say we need to sort this list into ascending order, because we want to be able to say, take the first integer here and know it is the smallest. There is a whole other can of worms here we will skip over, whether to sort now or search later… Well, a Bubble Sort simply takes the first integer, compares it to the next integer and says, if this is bigger than the one behind it, swap the two of them. Simple, right? We then go through the next two, and the next and the next. Swapping as need be. When we get to the end, we aren’t done though. Not even close. We have to start again, and go through the whole list, and again, and again, and again… Until we know that we have made no swaps, and then we will know we have got the whole thing sorted out so to speak. We must do this because well, if the largest number is the first in the list, well, we have to move it down the entire list. We only get to move it one space each time, so it will take going through the whole list as many times as there are items in the list before we finish, and once more to verify.
You can see how this sounds tedious, and while we aren’t doing any heavy lifting here ourselves. Spending the limited resources of any computer will in no short order bring everything to a grinding halt, like rush hour on I-405. So, the way we would denote the worst case would be in big O, O(n^2). Which is a whole other lesson that we might cover at some point, but let’s just say that when you exponentially increase the number of iterations with every additional number/ item, things aren’t very efficient.
So, how do we actually code this beast? Here, take a look at a sample function in Python 3.
# We define our list of random integers n = [1,5,8,2,10,11,4,3,9,7,34,56,23,46,6] # Define a function that will do the sorting, # named appropriately of course def bubble_sort(n): # We need to know when we have actually finished, # so we set a counter count = int # Our counter keeps track of how many position # swaps we make, when it's zero and we've gone through # the list, we know we are done while count !=0: count = 0 # We start a loop that goes to one number less than # our list, because our next statement compares the # current number to the one ahead of it # If our loop ran for the whole list, we would reference # a non existing number at the end. for i in range(len(n)-1): # Here we simply compare the current integer # to the one after it if n[i] > n[i + 1]: # If the one after is larger, # we swap the two positions n[i], n[i + 1] = n[i + 1], n[i] # Since we made a swap, we up the counter count += 1 # print a before and after here to see the magic happen print(n) bubble_sort(n) print(n)
So, there you have it. The infamous Bubble Sort! If that glossed over everything too quickly and you’re still scratching your head, don’t worry. I have a great book I will be reviewing here shortly that will bring programming in Python from a head against the wall proposition to just another skill in a fun and friendly manner. Thanks for listening, come back soon!