In this lesson, we are going to implement the bubble sort algorithm. To recap from our sorting algorithm overview, the bubble sort algorithm sorts a collection by moving from left to right, comparing a value with the next value to determine which value is higher (or lower depending on the goal). Typically it iterates through the entire list many times in order to properly sort a collection. As mentioned in the previous lesson, bubble sort is not effective for real-world programs because it's too slow.

Bubble Sort Code Example

We'll start off by creating a method called bubble_sort that takes an array as an argument.

def bubble_sort(array)
  n = array.length 
  loop do
  end
end

Next we assign the length of the array to a variable called n. From there we create a loop to iterate through the entire array. For this case we're going to use the generic loop mechanism, which operates very much like a while loop. Inside the loop we check the value of each element and compare it with the next one.

For example, let's say our array contains the following elements [1, 4, 1, 3, 4, 1, 3, 3]. First bubble sort compares 1 with 4, and does nothing because 1 is smaller. Next, it will check the next two values, which are 4 and 1, and will make the swap because 1 is lesser than 4. In the next iteration, it will look at 4 and 3, and will move 3 to the left. This algorithm will continue this way until the entire array is sorted.

We are going to create a boolean variable called swapped and set it to false. This is the variable that will be checked to determine when the program should exit the loop.

  loop do
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1]=array[i+1], array[i]
        swapped = true
      end
    end
  end

In this code you'll see that we're using a nested iterator that will run (n - 1) times. We're also going to use the block variable i. Inside this block we have a conditional where we are checking if a particular element in the array is greater than the next element, and if it's greater, then it swaps the elements. Once that's done, we'll set the swapped variable to true. We want to have the loop end when the swapped attribute has gone through the (n - 1) loop and has not been marked as true, which means that the array is sorted. In order to implement this sentinel value we'll add this code to the end of the loop:

break if not swapped

Lastly, let's return the sorted array back to the user by adding a call to array at the end of the method.

Let's test this method now with the code:

a = [1, 4, 1, 3, 4, 1, 3, 3]
p bubble_sort(a)

The entire code for this method is here:

def bubble_sort array
  n = array.length

  loop do
    swapped = false

    (n-1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1]=array[i+1], array[i]
        swapped = true
      end
    end

    break if not swapped
  end

  array
end

a = [1, 4, 1, 3, 4, 1, 3, 3]
p bubble_sort(a)

If you execute this, the output is:

[1, 1, 1, 3, 3, 3, 4, 4]

Which means that it's working perfectly and can sort an array.

So, you now know how to sort a list of values in Ruby using the bubble sort algorithm.