All Sorts of Things - Bubble Sort
15 Oct 2012
Let's take a look at the very much loved and very much hated bubble sort.
The bubble sort works by going through a list of values, comparing the values, and swapping them if they are in the wrong order. The list will be iterated over until there are no values left to swap. In my opinion, the most unexpected way to visualize it is here. Who would have thought, folk dancing and computer science. Pretty sweet, huh? Anyways, the term "bubble" comes from the way that the elements bubble up to the top of the list. If you read my post An Introduction to Big O Notation, you may like to know that the bubble sort is of O(n2) complexity.
An interesting thing to know about bubble sort is that it is a very controversial algorithm. It seems to be both very strongly loved and hated. Since it is a pretty simple algorithm, it is often taught in CS101 by people who love it(or at least find it useful) but there are some that strongly believe that it should not even be taught and go as far as to call it "the generic bad algorithm"! Read on and decide for yourself.
So let's say we have a list and we need to sort it. Let's call that list array.
1 array = [19, 24, 3, 4, 27, 12, 6, 6, 14, 15, 11, 2, 8, 13, 7] 2
Now let's create a bubble sort method that will conveniently accept an array.
1 def bubble_sort(array) 2 3 end 4
What we really want to do is create a way for the values to be compared to each other and to swap them if they are our of order. (smallest to largest) We need to check through the entire list comparing each adjacent value. Array? Each? Let's use an iterator! Now, one thing to keep in mind is that when we compare the current value to the value directly after it, if we move to the last value, we will have no next value to compare it to so let's subtract 1 off of the each so that we do not try to compare the last value against nothing.
1 def bubble_sort(array) 2 (array.length-1).times do |i| 3 if array[i] > array[i+1] 4 array[i], array[i+1] = array[i+1], array[i] 5 end 6 end 7 end 8 // 14 is what is returned from this method 9 // this is what the array would look like 10 //[3, 4, 19, 12, 6, 6, 14, 15, 11, 2, 8, 13, 7, 24, 27] 11
You may have noticed that it took care of moving the largest value to the bottom of the list but you also might be thinking, "That is a good start but hey!, most of my values are still out of order! AND that only returns the value 14!" Okay, Okay, you are right. Let's do something about it.First let's address the return value of 14. The 14 is returned as the amount of times that we iterated over the list of values and has nothing to do with sorting any of the numbers inside the array. Second, we need to be able to keep iterating over that list until it is finished swapping and when it is finished we want to get the array back not the amount of times it was iterated over. Let's use a variable with a boolean value to figure out if the value is finished sorting and let's add a loop that will stop when the boolean tells it to. Oh, and let's return the array at the end.
1 def bubble_sort(array) 2 loop do //beginning of the loop 3 swapped = false // set the boolean value to false on the outer loop 4 (array.length-1).times do |i| 5 if array[i] > array[i+1] 6 array[i], array[i+1] = array[i+1], array[i] 7 swapped = true //change the boolean value 8 end 9 end 10 break unless swapped //stop the loop if there is no more swapping to do 11 end 12 array //return the array 13 end 14
If you notice, even if only one value in the list was swapped, it will set swapped to true. This will force the loop to run again checking to see if anything needs to be swapped. Only in the case that nothing is swapped will the swapped value remain false. I kind of think of the last run through as the verification step.
That will work just fine but Let's add one more line for speed. Let's add something to check if the array is empty or has a value of one. If it does, we know that there will be nothing to sort and can just return the array.
1 def bubble_sort(array) 2 return array if array.length <= 1 //line that we just added 3 loop do 4 swapped = false 5 (array.length-1).times do |i| 6 if array[i] > array[i+1] 7 array[i], array[i+1] = array[i+1], array[i] 8 swapped = true 9 end 10 end 11 break unless swapped 12 end 13 array 14 end 15