Get Better at Ruby with Sorting Algorithms

Sorting algorithms are a great way for us to become better developers. They help us with logic and gives us a better understanding on how it all works behind the scenes, as we discussed on our last post.

Continuing with the series, in this post we will look at Bubble Sort, another simple yet very helpful algorithm. It its like an evolution to the selection sort, it iterates through the array several times and it too can be quite costly to run, but instead of keeping an stationary variable and comparing it with all the other values in the collection, it goes through it comparing the current value with the immediate next or previous one, swapping them if the current one is bigger or lesser than the one that we are comparing it to.

The advantage of the bubble sort is that, like said, it is very simple to understand and to execute, making it great for studies and even useful for small collections.

How it works 💭

There are some approaches to this algorithm, we will look at one where there is no waste in iterations. Just like in the selection sort, we will have a part of our array that is separated from the unsorted part, and we will delimit it by "pushing" the bigger number to end of our array. Lets see.

We have the following unsorted array, we will compare the numbers in pairs until we reach the end of the array. If the first value is bigger then the second one, we swap them.

4 1 5 3 2  >  1 4 5 3 2  >  1 4 5 3 2

This process is repeated until we reach the end of the collection. We would now have an array that looks like the following:

1 4 3 2 5

You can see that we "pushed" the number 5 - biggest in our array - to the last position. We no longer need to compare any other values to it as we know that it is the bigger in the array, so we put a delimiter to know that we will no longer use it.

1 4 3 2 | 5

We repeat the comparisons until we "push" the next bigger number to the end and then move the delimiter.

1 4 3 2 | 5  >>  1 3 2 4| 5   >>  1 3 2 | 4 5

The process will repeat until we have "pushed" all the bigger numbers to the end and the array is sorted.

1 2 3 4 5

Time to code 💻

We first implement the loop that will work as our delimiter. It starts at the last index of the array and will decrease to the first index (0), the downto Ruby method will do that for us. The 'i' variable will work like our '|' delimiter.

def bubble_sort(array)
    # Goes from the last index of the array to the first
    (array.length - 1).downto(0) do |i|
    end
end

The second loop will go through the unsorted part of the array. Starting at the second element - we will see why - until it reaches the delimiter 'i'.

# Goes from the second element to the demiliter
(1..i).each do |j|
end

Our second loop starts at the second element because it compares itself with the element behind it. The variable j checks if the value in j - 1 is bigger then itself and, if it is, they swap positions.

# Swaps the position of the elements if j-1 > j
swap(array, j - 1, j) if array[j - 1] > array[j]

swap is just a simple method that swaps the position of the two values using an auxiliary variable.

def swap(array, i, j)
    aux = array[i]
    array[i] = array[j]
    array[j] = aux
end

We now should have a code that looks like this:

def bubble_sort(array)
    # Goes from the last index of the array to the first
    (array.length - 1).downto(0) do |i|
        # Goes from the second element to the demiliter
        (1..i).each do |j|
            # Swaps the position of the elements if j-1 > j
            swap(array, j - 1, j) if array[j - 1] > array[j]
        end
    end

    # Returns the sorted array
    array
end

def swap(array, i, j)
    aux = array[i]
    array[i] = array[j]
    array[j] = aux
end

To test it we can just create an array and try to sort it

array = [4, 1, 5, 3, 2]
# Print unsorted array
p array
sorted_array = bubble_sort(array)
# Print sorted array
p sorted_array

And we should have a response that looks like this:

> ruby bubble_sort.rb
[4, 1, 5, 3, 2, 9, 15, 43, 34, 10, 7]
[1, 2, 3, 4, 5, 7, 9, 10, 15, 34, 43]

Simple as that! That was one more sorting algorithm for us to study logic and Ruby. Now go on and implement it yourself.

Let me know your thoughts and opinions on the current state of the series and what can be improved! 😃

Get Better at Ruby with Sorting Algorithms - Bubble Sort

How it works 💭

Time to code 💻