Selection Sort in Ruby

Hi all! Hope you had a wonderful Cinco de Mayo 🇲🇽 and also May the Fourth Be With You ⭐️

I'd love to jump back into this series with a less intricate sorting method: selection sort!

Overview

First, a little overview about the selection sort algorithm:

• Selection sort is an in-place sorting algorithm
  • A new array is not being created to store the sorted values, instead the values are being swapped within the original array
• Selection sort is our first algorithm in the series that doesn't involve recursion.
  • We are simply iterating over different points in the array until we reach the end.

Time Complexity

Like every good algorithm that would ever be needed in any good coding interview, we have to discuss the time complexity.

Time	Case
O(n2)	average case run time
O(n2)	worst case run time

Compared to our other friends, merge and quick sort, selection sort is very slow. Each value needs to be iterated over once, and if we have n values in the array, that easily becomes O(n²). It's extremely ineffective on large lists and performs worse than many of the other sorting algorithms.

Because selection sort is an in place sorting algorithm, it's space complexity is O(1) in worst case.

Theory/Break Down

Alright, let's go into the theory behind the selection sort algorithm. When I say theory I find it the most helpful to visualize what the actual process is and then we can code it up.

There are two distinct processes occurring in the selection sort algorithm: first the array is being iterated over to allow swapping of the values to occur and the second is that portions of the array are being iterated over multiple times to find the smallest value.

We keep track of the current minimum, the value that starts at the 0 index of the array initially and then increases as we continue iterating. We find the smallest value in the array and then swap it with the current minimum, and this continues until all of the values in the array have been swapped correctly and the array is sorted.

It is definitely less involved than the previous methods we've gone over and that makes it much simpler to understand and code up. As you can above, this process continues until the entire array is correctly sorted.

Actual Code

Alright, on to the part you've been probably waiting for, the code! This is just my implementation of selection sort in Ruby and you can feel free to play with it and change it around to whatever works best for you.

def selection_sort(array)
  current_minimum = 0
   while current_minimum < array.length - 1
    smallest_value_index = find_smallest_value_index(array, current_minimum)
    array[current_minimum], array[smallest_value_index] = array[smallest_value_index], array[current_minimum]
    current_minimum += 1
  end
  return array
end

def find_smallest_value_index(array, current_minimum)
  smallest_value = array[current_minimum]
  smallest_index = current_minimum
    while current_minimum < array.length
      if array[current_minimum] < smallest_value
        smallest_value = array[current_minimum]
        smallest_index = current_minimum
      end
    current_minimum += 1
    end
    return smallest_index
end 

For a little clarification in the code and to match the theory that was previously explained, we only need to iterate through the array as many times as the length of the array minus 1. This is because we know that our last value left in the array will be correctly sorted after the second to last value is swapped.

We use our helper function, find_smallest_value_index, to get the array index of the smallest value. This is returned and that value is swapped with the first element in the array, or our current minimum.

After the first swap, each time find_smallest_value_index goes over the array to find the smallest value and its index, it is overlooking the values that have already been swapped and consequently are sorted. Thus, our new current minimum is always larger after each iteration. This way the first index doesn't just get swapped over and over again with the next value in line.

My apologies for the wordy function and variable names, but I wanted it to be very clear what each variable in the code was representing. Don't worry, you can always rename them later when you make sense of the code for yourself. 😊

Resources

And of course, a few helpful resources if you want to see the selection sort algorithm in action:

selection sort videos:

• https://www.youtube.com/watch?v=GUDLRan2DWM
• https://www.youtube.com/watch?v=g-PGLbMth_g

I hope that this could be helpful for you and I'll catch you for the next installment of my sorting algorithm series! Happy coding 😊

Comments

[Matthieu]

Hey Megan,
thanks for keeping up with this series, these sorting algorithms are really interesting.

I'm not sure about the -2, as when I tested with [10, 1, 64, 89, 12, 0] for example, there is one sort missing I think, as it resulted with [0, 1, 10, 12, 89, 64].

Also I guess you could reduce your code a little bit, using for instead of while, and not using smallest_value, as it is related to smallest_index value, which is what you really want here.

def selection_sort(array)
   for index in 0...array.length - 1
    smallest_value_index = smallest_value_index(array, index)
    array[index], array[smallest_value_index] = array[smallest_value_index], array[index]
  end
  array
end

def smallest_value_index(array, from_index)
  smallest_index = from_index
    for index in from_index...array.length
      if array[index] < array[smallest_index]
        smallest_index = index
      end
    end
    smallest_index
end 

[Megan]

Hi Matthieu,

I've really started to look forward to your comments because I feel like they are so helpful and are making me a better coder. So thank you, I really appreciate you! And I also appreciate you following with the series too.

I completely agree with your comment on the -2 and have fixed that in my code, thanks for catching that!

Also, I definitely went back and forth on my naming for the smallest_value, so I'm glad you felt the same way haha.

I'll catch you on the next post 😊

[Matthieu]

Hey Megan,
I'm glad my comments could help ! I'm looking forward to your next post :)