Selection sort is a straightforward sorting algorithm. This algorithm search for the smallest number in the elements array and then swap it with the element at the first position, then it searches for the second smallest number and swaps it with the element in the second position, and it will continue doing this until the point when the whole array is arranged. It is called selection sort since it more than once chooses the following littlest component and swaps it into the ideal place.
Selection sorting algorithm is not appropriate for a large number of datasets as its average and worst case complexities are Ο(n2), where n is the number of items.
How Selection Sort Works?
Following are the steps associated with selection sort (for arranging a given element array in ascending order)
1. Beginning from the primary element, we look through the smallest component in the element array and supplant it with the component in the first position.
2. We at that point proceed onward to the second position, and search for littlest component present in the subarray, beginning from record 1, till the last list.
3. We supplant the component at the 2nd position in the original array.
4. It will continue doing this until the point when the whole array is arranged.
C# Program for selection Sort
using System;
class Program
{
static void Main(string[] args)
{
int ArrayLength = 10;
int[] array = new int[10] { 125, 50, 10, -6, 20, 60, 80,-10, 90, 45 };
Console.WriteLine("The Array elements Before the Selection Sort is: ");
for (int i = 0; i < ArrayLength; i++)
{
Console.WriteLine(array[i]);
}
int tmpIndex, min_key_index;
for (int j = 0; j < ArrayLength - 1; j++)
{
min_key_index = j;
for (int k = j + 1; k < ArrayLength; k++)
{
if (array[k] < array[min_key_index])
{
min_key_index = k;
}
}
tmpIndex = array[min_key_index];
array[min_key_index] = array[j];
array[j] = tmpIndex;
}
Console.WriteLine("The Array elements After the Selection Sort is: ");
for (int i = 0; i < 10; i++)
{
Console.WriteLine(array[i]);
}
Console.ReadLine();
}
}
|
Complexity Analysis of Selection Sort
Selection Sort use two nested for loops to complete sorting
So for n size of the array, the following will be the complexity for the selection sort algorithm:
Best Case Time Complexity [Big-omega]: O(n2)
Worst Case Time Complexity [ Big-O ]: O(n2)
Space Complexity: O(1)
Average Time Complexity [Big-theta]: O(n2)
