Ashok
Ashok's Blog

Follow

Ashok's Blog

Follow

Selection Sort

Ashok's photo
Ashok
·Jan 14, 2020·
Play this article

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.

Selection-Sort.PNG

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;

}
 
Share this