Selection Sort

Selection sort , also known as in-place comparison sort, is about selecting the smallest element in the list and placing it in the right position.

The algorithm divides the input list into two parts.

• Sorted Sublist

• Unsorted Sublist

To start with, the sorted sublist will be empty and all the values will be in the unsorted sublist.

For each iteration of the selection sort ,

1. Search for the smallest element in the unsorted list.

2. Place it at the end of the sorted sublist.

Time complexity

The time complexity of selection sort is O(n^2)

Worst case performance : O(n^2) , when we want to sort a list in ascending order, but it is arranged in descending order.

Average case performance : O(n^2) . When the list is in random order.

Best Case : O(n) . When the list is already in sorted order.

Selection sort in C#

static int[] SelectionSort(int[] input)
{
    var length = input.Length;

    for (int i = 0; i < length - 1; i++)
    {
        var minValueIndex = i;

        for (int j = i + 1; j < length; j++)
        {
            if (input[j] < input[minValueIndex])
            {
                minValueIndex = j;
            }
        }
        (input[i], input[minValueIndex]) = (input[minValueIndex], input[i]);
    }
    return input;

}