Sorting algorithms are great, as is Ruby. We can combine them to become better developers. Sorting algorithms will help you with programming logic, and doing them in Ruby will increase your knowledge in the language.
As a new years resolution I wanted to start writing and blogging (it was a 2021 resolution but lets not worry about that) and I've been messing with Ruby for the last few months. So I decided to take the opportunity and merge the two.
I'll make this a series as we go through some algorithms and learn some Ruby together. I hope this helps and/or motivates some fellow rubyists or folks wanting to start blogging.
But what are sorting algorithms?
They, well... sort elements in a collection. They are used to rearrange the elements of an collection given a conditional comparison. It can be numerical, lexicographic, etc. You can even specify your own custom condition to rearrange your collection based on your needs.
Its uses vary from basics such as an ascending numerical order to perform a binary search to more complex cases, on the implementation of the clause ORDER BY in an SQL database for example.
The selection sort
It's one of the most simple sorting algortihms, great to get started. It works by iterating through the collection, finding the maximum or minimum element - dependind on what you want -, placing it at the beginning and repeating this process until the collection is sorted.
The problem with it is that it is too costly to run, especially when dealing with large collections of data. It iterates too many times on itself. Let's see.
We have the given array and will start our comparison from the first element, setting it as the starting minimum value. The arrow represents the index that marks the beginning of the elements that will be compared:
V
[ *7* 4 1 3 8 ]
It will iterate trhough the array and find the actual minimum. When it does, it will replace it with the value thats being compared to (on the arrow):
V V
[ 7 4 *1* 3 8 ] >> [ *1* 4 7 3 8 ]
Now the arrow moves, a new iteration starts from it until it finds the minimum value:
V V V
[ 1 *4* 7 3 8 ] >> [ 1 4 7 *3* 8 ] >> [ 1 *3* 7 4 8 ]
This process will repeat untill the arrow reaches the last index and all the elements are sorted.
Lets implement it in Ruby
The variable 'i' is our arrow. On the first loop - the one that controls the array from the beginning to the end - we set the '_min_value_' to the value inside the index of the arrow and create an auxiliary variable '_aux_index_' that will hold the index of the minimum value of the array.
def selection_sort array
i = 0 # Equivalent to the arrow
while i < array.length
min_value = array[i]
aux_index = i
end
end
Below that will go the second loop. This one iterates through the unsorted part of the array - the one in front of the arrow -, finds wich value is the next minimum and saves its index.
...
(i..array.length - 1).each do |j|
if array[j] < min_value
min_value = array[j]
aux_index = j
end
end
Now we have the next minimum value and its index on the array, what is left is to make the swap, that is, put the minimum value in the index of the arrow and put the value that was in the arrow where the new minimum value was.
# Where the minimum value was gets the element in the arrow
array[aux_index] = array[i]
# The arrow gets the new minimum value
array[i] = min_value
# We move the arrow foward for the next iteration
i += 1
That's it, now we return the sorted array. Our complete function will look something like this:
def selection_sort array
i = 0 # Equivalent to the arrow
while i < array.length
min_value = array[i]
aux_index = i
(i..array.length - 1).each do |j|
if array[j] < min_value
min_value = array[j]
aux_index = j
end
end
# The swap 👇
# Where the minimum value was gets the element in the arrow
array[aux_index] = array[i]
# The arrow gets the new minimum value
array[i] = min_value
# We move the arrow foward for the next iteration
i += 1
end
array
end
To test it we can create an array with some elements, shuffle it using Ruby's own method and then sort it.
array = (1..10).to_a
array.shuffle!
p array
p selection_sort array
The result should be something like this:
❯ ruby selection_sort.rb
[4, 6, 9, 2, 8, 7, 3, 5, 10, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
That's it, we implemented our first sorting algorithm in Ruby. It is a rather basic one, but it's just the beginning. Stay tunned for the next posts as we implement more complex algorithms and advance in Ruby together. If you have any doubts or suggestions for the continuation of the series or in general, please let me know.