Selection Sort Explained

Introduction

If you are trying to get a remote job in a top IT consulting company, you will definitely fall into a live code exercise where your algorithms, logical thinking and problem solving skills will be tested and you will have to demonstrate a solid knowledge of these concepts.

Today I decided to write about a type of sorting algorithm that I found several times in interviews and decided, after studying the approach used, to create an initial solution in the simplest possible way.

Understanding the logic

As we know, the sort algorithm basically uses three basic principles to sort the items in a list. A comparator, a swap function, and recursion. For this selection sort algorithm I will focus in the first two.

Given that we have the following list of numbers: 64, 25, 12, 22, 11, how would we use selection sort to swap and sort the list in an ascending order?

The following code from the init function uses two for loops to create a temporary list (line 2) with the remaining values of the original list, which will be shorter in each new loop.


For each temporary list created we determine what is the minimum value for each new list (line 6) and get its position in the original list (line 7) so that we can change or order it. Basically, we have the follwing four steps.

1. Get the minimum value from the list
2. Get the position of the value in the list
3. Check if the item is not ordered
4. Swap/sort the item in the original list

With the first item of the list sorted, we skip it and create a new temporary list with the remaining values to obtain the next minimum value of the list to be swaped, repeating the steps from 1 to 4 until the end of the list. and in case the item is not in the sorted position we apply the logic of the swap function so that we can sort it by placing it in the next position of the original list.

The swap function will get the value of the current index in the list (line 2) and swap it with the value that is in the position of the next minimum value (line 3 and 4).

Full Code

Code Execution

Conclusion

If you are studying for a remote position it is a good idea to take the time to delve into algorithms, data structures and design patterns.

Github

GitHub Repo

References

Learning Algorithms
Algorithms in a Nutshell
Design Patterns