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(n2). 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:
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 😊
Top comments (3)
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.
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 😊
Hey Megan,
I'm glad my comments could help ! I'm looking forward to your next post :)