In this article I will help you to understand one of the sorting algorithm in software development. I am talking about selection algorithm sort in C#. Most of the articles I have seen only provide you the code with little understanding of the core logic.
Selection sort algorithm in C#
Lets first try to understand the algorithm with the help of figure below.
Suppose I have an unsorted array of numeric elements. The array is {6,1,7,8,9,3,5,4,2} as shown in the first step of below figure.
In selection sort we will maintain a pointer starting from the first element. We will move this pointer the next locations as we move forward.
Using linear search we will find the smallest element in the array. As we can see in the figure above, the smallest element is at position 1 and its value is also 1.
Now we will swap the element at position 0 with the smallest element.
In the step 2, you can see the two swapped elements. And we will consider the first element as fully sorted. Now we will search the smallest element beginning from second element i.e. position 1.
And the next smallest element will get is 2 at the last position, we will swap 6 and 2. Resulting the array after this is in the step 3. Finally our array is sorted till position 1.
Now our sub array sequence will be starting from position 2 and on wards.
We will continue doing this finding and swapping till we will reach the last element.
The code for Selection sort algorithm in C# is quite simple.
private static void SelectionSort()
{
int[] arr = { 6, 1, 7, 8, 9, 3, 5, 4, 2 };
int pos = 0;
while (pos <= arr.Length -1)
{
int smallestElementPosition = SmallestElementPosition(pos, arr);
if (arr[pos] > arr[smallestElementPosition])
{
//Swap the elements if the element at the pointer //is greater than the smallest element in the sequence
arr[pos] = arr[pos] + arr[smallestElementPosition];
arr[smallestElementPosition] = arr[pos] - arr[smallestElementPosition];
arr[pos] = arr[pos] - arr[smallestElementPosition];
}
pos++;
}
Array.ForEach(arr, (item) => Console.WriteLine(item));
}
/// <summary>
/// The method is used to get the position of the smallest elment from the sequence
/// </summary>
/// <param name="startPos"></param>
/// <param name="arr"></param>
/// <returns></returns>
private static int SmallestElementPosition(int startPos, int[] arr)
{
int smallestElement = Int32.MaxValue;
int elementPos = startPos;
for (int i = startPos; i < arr.Length; i++)
{
if (arr[i] < smallestElement)
{
elementPos = i;
smallestElement = arr[i];
}
}
return elementPos;
}Run Time Complexity:
The outer while loop executes the number of time equal to number of elements in the array. Suppose the number of elements in array are {n}.
Than the method SmallestElementPosition is executed n number of times. Suppose for the first element it starts from the zero index and executes till last element. It means it executes upto n times in worst case.
For second element it starts with index 1 and executes till n. It means it executes till (n-1) times in worst case.
We will get below equation for all elements:
n + (n-1) + (n-2) + (n-3)…+ 1 + 0
which is equivalent to n(n+1)/2.
And it results to (n^2 + n)/2. Removing all the constants we get n^2.
Therefore the rum time complexity of selection sort algorithm in quadratic i.e. n^2.
Conclusion:
I hope this article will help you to understand the selection sort algorithm with strong concept.