Follow

Follow

# Selection Sort

Ashok
·Jan 14, 2020·

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;

}
``````