Meet the patriarch of the sorting algorithm family! Selection Sort is the beloved father and grandfather to the rest of the gang.

He's old, and likes things done a certain way, but at the heart of it all he's a family man with a penchant for handing out Dum Dums and lecturing young'uns about days gone by. He and his darling wife Merge Sort will be doing the hosting duties for the family reunion at their large familial home, complete with an acre of land and a dog who quite enjoys chasing the kids around.

Ma! Come look at this! The dog got one o' them squirrels again!

Boy, does he love that dog. Even better, the dog loves him. It won't leave his side for a moment, except to chase the occasional squirrel, rabbit, or toddler. He's getting up there in years, though, and Selection Sort dreads the day he has to explain to his young grandchildren where their beloved pet Rhythm has gone.

Selection Sort is one of the easiest sorting algorithms to understand, but also one of the worst-performing. That makes it a perfect candidate to kick off the reunion!

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound
Project for this post: SelectionSort

Algorithm

  1. FOR EACH item in the collection...
  2. ASSUME the first item in the considered range is the smallest value
  3. ITERATE through the rest of the collection
  4. SWAP the smallest found value with the current value. This value is now sorted.
  5. ADJUST the considered range to exclude the now-sorted value.
  6. GO TO 2, CONTINUE until all elements have been sorted in this manner.

Visualization

The red box is the found lowest value. Yellow values are a sublist of the total list and have already been sorted; therefore the "considered range" mentioned in the algorithm above is all values that are not yellow. The blue value is the currently scanned value.

You may notice from watching this animation that this algorithm has to iterate through the collection many times. As discussed below, this is a major reason why this algorithm is not very efficient.

Also check out this really cool "visualization and audibilization" of Selection sort from YouTube:

C# Implementation

class SelectionSort
{
    static void Main(string[] args)
    {
        int[] array = new int[15] { 45, 72, 58, 92, 26, 4, 13, 90, 81, 15, 33, 36, 47, 8, 54 };
        int count = 15;
        Console.WriteLine("Selection Sort");

        //First, output starting state of the array
        CommonFunctions.PrintInitial(array);

        int temp, smallest;

        //The algorithm builds the sorted list from the left.
        //1. For each item in the array...
        for (int i = 0; i < count - 1; i++)
        {
            //2. ...assume the first item is the smallest value
            smallest = i;
            //3. Cycle through the rest of the array
            for (int j = i + 1; j < count; j++)
            {
                //4. If any of the remaining values are smaller, 
                //   find the smallest of these
                if (array[j] < array[smallest])
                {
                    smallest = j;
                }
            }
            //5. Swap the found-smallest value with the current value
            temp = array[smallest];
            array[smallest] = array[i];
            array[i] = temp;
        }

        //Output final state of the array
        CommonFunctions.PrintFinal(array);

        //We call ReadLine here to avoid noisy output in the command line.
        Console.ReadLine();
    }
}

Time and Space Complexity

Selection sort is a poor-performing sort. It needs to iterate over the entire unsorted portion of the collection before it can move values, regardless of whether it has already located the lowest known value. Because of this, as shown above, it always has a time complexity of O(n2).  

This is one of the worst time complexities that is regularly seen in sorting algorithms and essentially means that the time to complete the sort is a function of the square of the number of items to be sorted.  

What's nice about Selection Sort (kind of) is that the space complexity is O(1), meaning the algorithm requires no additional space beyond what is used to store the collection. In other words, it can be implemented without consuming additional memory, which is a point in its favor, though not a large one.

Summary

Selection Sort is one of the simplest sorts to understand and to write, but performs terribly. It's mostly of interest as a thought exercise, but don't tell him that. He might set the dog on you.

In the next post in this series, we take a look at Merge Sort, Selection Sort's loving wife and matriarch of the family. Just watch out for the lasagna.

Merge Sort in C#
Merge Sort is the matriarch of the sorting algorithm family. A source of wisdomfor all her children (and a not-insignificant amount of “I told you so”), she isconstantly looking out for her beloved sons and daughters. The land on which the familial home sits has been in her family for generation…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project on GitHub to see more members of the sorting family reunion!

Happy Coding!