By Note: This is part 2 of a series looking at different sorting algorithms with Ruby. Part 1 explored bubble sort.
In this post, I'll be walking through how to implement a selection sort algorithm with Ruby. Selection sort is an in-place comparison sorting algorithm. This means that sorted items occupy the same storage as the original ones. Before we go any further, it's important to note that the selection sorting algorithm is not commonly used in practice unless the dataset is small (i.e., 10-20 elements). However, it's a great starter algorithm to learn and understand, similar to learning how to ride a tricycle before a bicycle, if you will. The implementation might show up on a coding challenge for a job interview, or you might be asked to explain why an algorithm like selection sort would not be very practical on a large dataset. Selection sort does usually outperform bubble sort, which is the first algorithm we looked at in this series.
At a high level, selection sort divides the array into two parts: one half sorted and the other not. At the onset, the sorted section is empty, and the unsorted portion contains all of the elements. Selection sort utilizes two loops; the outer loop iterates n times, where n is the number of elements in the array. We immediately set the "min index" to the first element, and then use another loop to compare elements, swapping the min index if the adjacent element is less than the current minimum.
If this is hard to follow, don't worry! We're going to walk through an actual example next. :)
Step By Step
Let's start with an array with the following elements: [10, 30, 27, 7, 33, 15, 40, 50]
Iteration one: Find the smallest number
In this case, the smallest number is 7, so we place it at the beginning and move 10 to where the 7 was. Our array now looks like this: [7, 30, 27, 10, 33, 15, 40, 50]
Iteration two: Find the next smallest number
Starting at the element in index position 1 (remember, arrays are 0-indexed), find the next smallest element
In this case, it is 10. Move 10 to the second position in the array and move 30 to where the 10 was. The resulting array is this: [7, 10, 27, 30, 33, 15, 40, 50]
From here, we continue this exact process until our array is fully sorted. Below, you can see the resulting arrays after the next iterations.
Iteration three:
[7, 10, 15, 30, 33, 27, 40, 50]
Iteration four:
[7, 10, 15, 27, 33, 30, 40, 50]
Iteration five:
[7, 10, 15, 27, 30, 33, 40, 50]
Bingo! We are sorted!
If you're more a visual learner, here is an example of how a selection sort would work with an array of []
A Ruby Implementation
Here is a selection sort function written in Ruby:
def selection_sort(array)
n = array.length - 1
n.times do |i|
min_index = i
for j in (i + 1)..n
min_index = j if array[j] < array[min_index]
end
array[i], array[min_index] = array[min_index], array[i] if min_index != i
end
puts array
end
Let's look at how this works.
First, we set n equal to the number of elements. Remember, we need to subtract one because arrays are 0-indexed.
Next, we create our outer loop, which is going to run n times.
min_index = i
Here, we are setting the minimum index to the element in the first position.
for j in (i + 1)..n
Next, we create our inner loop. This line is saying "for the element in the second position to the nth element, do what follows". If you aren't familiar with the .. operator, it creates a range from the start point to the endpoint, inclusively. For example, 1..10 creates a range from 1 to 10, inclusive.
min_index = j if array[j] < array[min_index]
Inside this loop, we set the min_index to a new element if it less than the current min_index.
array[i], array[min_index] = array[min_index], array[i] if min_index != i
Outside of our inner loop, we look to see if the current min_index is equal to i. If this is true, we need to shuffle our elements. We set array[i] to array[min_index] and array[min_index] to array[i]. Here, we are performing the "swap" the same as we did in our example.
Finally, once we are finished, we output our array, which is now sorted!
Putting it All Together
Here is my full program:
def selection_sort(array)
n = array.length - 1
n.times do |i|
min_index = i
for j in (i + 1)..n
min_index = j if array[j] < array[min_index]
end
array[i], array[min_index] = array[min_index], array[i] if min_index != i
end
puts array
end
array = [10, 30, 27, 7, 33, 15, 40, 50]
selection_sort(array)
Running ruby ruby-selection-sort.rb from the terminal outputs the following:
7
10
15
27
30
33
40
50
Cool!
Understanding Why Selection Sort is Inefficient
One way to measure an algorithm's efficiency is to look at the "Big-O notation"; this represents the worst-case performance so that algorithms can be compared. For example, an algorithm with a Big-O of O(1) means that the worst-case run time is constant as the number of elements, "n", grows, whereas an algorithm with a Big-O notation of O(n) means that the worst-case run time increases linearly as n grows. This means that if you have an array with 100 elements and must choose between sorting algorithms that are O(n) and O(1), you would choose the O(1) algorithm because O(1) definitely beats O(100).
Like the bubble sort, the selection sort has a worst-case and average complexity of O(n^2) because of the nested loops. This means that its efficiency decreases dramatically as the number of elements grows.
Wrapping Up
All things considered, selection sort is still an interesting algorithm that may pop-up in a coding challenge. Or, you may be given a selection sort function and asked what the Big-O notation is and why. Hopefully, the examples in this article will help you be ready to tackle either scenario.
