Understanding Selection Sort with Ruby

If I asked you to sit down right now and sort a list of numbers, there's a good chance that you'd intuitively rediscover the selection sort algorithm. It's a simple approach that can have significant performance implications. That's why it shows up so frequently in technical interviews - even though most developers never implement sorting from scratch. In this article, Julie Kent walks us through the selection sort algorithm, builds a working implementation in Ruby, and discusses its performance characteristics.

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 []

Selection sort visually Photo credit

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]
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  puts array

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]
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  puts array

array = [10, 30, 27, 7, 33, 15, 40, 50]


Running ruby ruby-selection-sort.rb from the terminal outputs the following:



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.

What to do next:
  1. Sign up for a FREE Honeybadger account
    Honeybadger helps you find and fix errors before your users can even report them. Get set up in minutes and check monitoring off your to-do list.
    Try Honeybadger for FREE
  2. Get the Honeybadger newsletter
    Each month we share news, best practices, and stories from the DevOps & monitoring community—exclusively for developers like you.
    author photo

    Julie Kent

    Julie is an engineer at Stitch Fix. In her free time, she likes reading, cooking, and walking her dog.

    More articles by Julie Kent
    Stop wasting time manually checking logs for errors!

    Try the only application health monitoring tool that allows you to track application errors, uptime, and cron jobs in one simple platform.

    • Know when critical errors occur, and which customers are affected.
    • Respond instantly when your systems go down.
    • Improve the health of your systems over time.
    • Fix problems before your customers can report them!

    As developers ourselves, we hated wasting time tracking down errors—so we built the system we always wanted.

    Honeybadger tracks everything you need and nothing you don't, creating one simple solution to keep your application running and error free so you can do what you do best—release new code. Try it free and see for yourself.

    Try Honeybadger for FREE
    No credit card needed - Simple 5-minute setup

    Learn more

    "We've looked at a lot of error management systems. Honeybadger is head and shoulders above the rest and somehow gets better with every new release."
    — Michael Smith, Cofounder & CTO of YvesBlue

    Honeybadger is trusted by top companies like:

    “We've looked at a lot of error management systems. Honeybadger is head and shoulders above the rest and somehow gets better with every new release.” 
    Michael Smith
    Try Honeybadger for FREE