Bubble bonanza

The title of this blog post is somewhat misleading. Over the past few days there has been more of a bubble catastrophe rather then a bubble bonanza.

I’ve been working on the Bubble sort algorithm which essentially takes and unsorted list, compares each number to the adjacent number and swaps them if the number on the left is smaller than the one on the right. This swapping continues until the whole list is sorted.

Although I understood the premise of what I needed to do, I couldn’t work out how to get over the final hurdle: keep swapping until the list is sorted.

If we take the example:

  list = [3, 3, 2]
  (0..(list.length - 2)).each do |i|
if list[i] > list[i+1]
a = list[i]
list[i] = list[i+1]
list[i+1] = a
end
end
list #1st time round = [3, 3, 2] | 2nd time = [3, 2, 3]

Looking at the example above, on the second iteration, if we swapped the numbers [3, 2] then we would need to check the whole list again to make sure the list is in fact sorted but we only loop over the list once.

Just swapping 1 pair of numbers sorts those two numbers but leaves the rest of the list unsorted [3, 2, 3]. We need another iteration to sort the list properly.

I paired with the infamous Felipe and we discussed how we’d be able to tell if the list was sorted. If the list is unsorted, we’d need to swap numbers, if it’s sorted we don’t.

We needed a way of tracking whether swaps were made while we were iterating through the list. This is the final solution we came up with which does exactly what we need.

def self.sort(list)
swapped = true
until swapped == false
swapped = false
(0..(list.length - 2)).each do |i|
if list[i] > list[i+1]
a = list[i]
list[i] = list[i+1]
list[i+1] = a
swapped = true
end
end
end
list
end

First we define a variable called swapped and give it the value of true which means we enter the until loop, swapped is then set to false and we start iterating through the list.

If swaps are made, at the bottom of the code block we give swapped the value of true and we loop again.

If each element is smaller than the next then no swaps need to be made and we can’t meet the condition of the if statement. Swapped’s value is unchanged and remains false.

Therefore, we meet the until loop’s condition, stop looping, exit the loop and return the list which is now sorted!