This is the first post in a series where we look at various sorting algorithms you’ll need to know for your next coding interview.

I struggled with understanding basic sorting algorithms when i first encountered them in college. I tried everything  from re-reading lecture slides, watching recorded lectures, implementing the algorithms in code etc. But invariably after couple of days, I’d get the different algorithms mixed up.

Then one of our professors showed me a very simple technique to understand, remember and practice these sorting algorithms. The technique is deceptively simple – just take the unsorted array and write down the transformations to the array at each step when applying the sorting algorithm. And do it on a handwritten piece of paper – not in your mind, not in PowerPoint or Visio and definitely not in code before you have a thorough understanding. Finally, repeat the process every couple of days till this get’s in your head.

Selection Sort is too simple of an algorithm to show up in your next Microsoft or Google coding interview. However, we’re starting the series here so that you can get an quick introduction to the “paper-based” problem solving and visualization method before delving into more complicated sorts you might actually face on your next FAANG or Microsoft interview.

Strategy for Selection Sort

Given an unsorted array of integers, we want to sort them in ascending order. The array under consideration is shown below:

Unsorted array to be sorted with selection sort

Here is the strategy:

1. Select one element in the array, starting with the first element.
2. Compare it to all other elements in the array sequentially.
3. If an element is found to be smaller than the currently selected element, swap their positions.

Note that the correct position for the selected element is found before moving on to next element in the array.

Visualize the algorithm on paper

This is the most critical part of understanding the algorithm. I’d suggest understanding the process of sorting as shown below and doing it yourself a few times till you can get the array to the correct sorted state.

Practice the algorithm on a piece of real paper or whiteboard ! You should try to write your own explanation at each step – this’ll help you reinforce and remember what you’re doing.

Selection Sort First Iteration

Above is the state of the array after the first iteration of the outer loop. 1 is indeed the smallest element in the array and should be in the first position. We are now done comparing the element in the first position in the array to every other element in the array.

Next we move to the second slot.

Selection Sort Second Iteration

We’re done with the second iteration. We can see that 2 is indeed the second smallest element and now the first two slots in this array are sorted.

Next move to the third slot and compare it’s element to every other element, swapping as necessary.

Selection Sort Third Iteration

The process continues till the entire array is sorted.

Implementing Selection Sort in C#

using System;

namespace Sorting
{
    class SelectionSort
    {
        public static bool debug = false;
        public static void Sort(int[] inputArr)
        {
            for(int i=0; i < inputArr.Length; i++)
            {
                for(int j= i+1; j < inputArr.Length; j++)
                {
                    if(inputArr[i] > inputArr[j])
                    {
                        Utilities.Swap(inputArr, i, j);

                        // Turn this flag on if you want to
                        //understand the state of the array after each Swap
                        if(debug)
                        {
                            Utilities.PrintArray(inputArr);
                        }
                    }
                }
            }
        }
    }
}

Analysis of Selection Sort

​

When to use and when to avoid Selection Sort ?

Use selection sort in the following scenarios:

1. When the array is NOT partially sorted
2. When we have memory usage constraints
3. When a simple sorting implementation is desired
4. When the array to be sorted is relatively small

Avoid using Selection sort when:

1. The array to be sorted has a large number of elements
2. The array is nearly sorted
3. You want a faster run time and memory is not a concern.