Selection Sort

Today, we begin to look at sorting algorithms. They are important because sorting is often used to simplify and optimize other algorithms.

The choice of the right sorting algorithm depends on

1. Data size - any algorithm is acceptable for small datasets as execution time will not be that different. However, you will want to pick an efficient algorithm with acceptable worst case runtime for large data sets.
2. Memory requirement - most algorithms are efficient only if they can reside in the memory. If memory is premium, an in-place algorithm may be a better choice

Selection Sort

Selection sort is the easiest to understand and implement; however, they are not particularly efficient as you will see later.

The general idea of this algorithm is

1. Start with the first element
2. Scan through the rest of the collection to find the element with the smallest key
3. Swaps the elements after scanning
4. Repeat with each subsequent element until the last element is reached

Rundown

Stability

Selection sort is considered to be unstable because it doesn’t preserve the input ordering of the elements. The initial ordering information is lost when the keys are swapped. Consider sorting of $[ 5_1, 3, 5_2, 2]$ with selection sort. After the first iteration, the array will look like this $[2, 3, 5_2, 5_1]$ and the initial ordering information is lost.

To get around element swapping, one can choose to insert the elements instead. In this case, the choice of a typical array is no longer a good choice as insertion operation requires O(n) ; thereby giving up the best part about selection sort of swapping elements in constant time even though it doesn’t increase the overall time complexity of O(n^2) Thus, it is important to look at other data structures like linked list which allows a constant time insertion.

Example Implementation

I implemented a generic selection sort with iterative approach.

public static void SelectionSortIterative<T>(T[] items) where T : IComparable
{
   int smallestItemIdx = 0;
   for (int i = 0; i < items.Length; i++)
   {
   	//Step - 1: start with the first element
   	smallestItemIdx = i; 

   	//Step - 2: scan through the rest of the collection to find smallest item
   	for (int j = i + 1; j < items.Length; j++)
   	{
   		if (Comparer<T>.Default.Compare(items[j], items[smallestItemIdx]) < 0)
   		{
   			smallestItemIdx = j;
   		}
   	}

   	//Step - 3 : swaps the items
   	Swap(items, smallestItemIdx, i);

   	//Step - 4: repeat till the last item
   }

private static void Swap<T>(T[] items, int idx1, int idx2) where T : IComparable<T>
{
   (items[idx1], items[idx2]) = (items[idx2], items[idx1]);
}