Sorting is one of the most common problems that programmers solve while building applications. Selection sort is one of the algorithms that we can use to sort elements in an array. We are going to learn how to implement selection sort in C# and analyze how the algorithm performs when sorting arrays of various sizes.
Let’s start.
What Is Selection Sort?
The goal of the selection sort algorithm is to find the minimum value of an array by iterating through each element. For each iteration, the algorithm compares the current minimum value of the array with the current element. If the current value is smaller than the minimum value, a swap process occurs. This process continues until the array is completely sorted.
Let’s learn how selection sort in C# works and understand its time and space complexity.
Selection Sort Algorithm In C#
Let’s assume we have an array of five numbers we need to sort in ascending order:
int[] array = { 40, 10, 20, 30, 50 };
First, we find the minimum value from elements 0 to 4 (indexes) and place it at position 0. The minimum value is 10. Since 40 is currently on position 0 we are going to swap it with 10:
10, 40, 20, 30, 50
Then, we check the elements 1 through 4 and place the smallest value at position 1. In this case, 20 is the minimum and we swap it with 40:
10, 20, 40, 30, 50
Next, we check positions 2 through 4 and set the minimum value (30) to position 2:
10, 20, 30, 40, 50
Let’s learn how to implement Selection Sort in C#.
How to Implement Selection Sort in C#?
First, we are going to define an array property NumArray that we are going to use to implement selection sort:
public int[]? NumArray { get; set; }
As the next step, we are going to create a SortArray method that iterates through the NumArray and sorts it in place:
public int[] SortArray()
{
var arrayLength = NumArray.Length;
for (int i = 0; i < arrayLength - 1; i++)
{
var smallestVal = i;
for (int j = i + 1; j < arrayLength; j++)
{
if (NumArray[j] < NumArray[smallestVal])
{
smallestVal = j;
}
}
var tempVar = NumArray[smallestVal];
NumArray[smallestVal] = NumArray[i];
NumArray[i] = tempVar;
}
return NumArray;
}
We can see that the algorithm uses two nested loops during the sorting process. We define two variables (tempVar and smallestVal) that hold values during the sorting process. As the outer loop iterates, smallestVal holds the current position of the array while the inner loop compares the current minimum value to the rest of the elements.
If the value of the array element is smaller than the current minimum value, swapping occurs. This process stops when the outer loop hits its arrayLength limit.
We can go ahead to verify that the method returns a sorted array:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new Selection();
sortFunction.NumArray = array;
var sortedArray = sortFunction.SortArray();
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);
Time and Space Complexity of Selection Sort
For each iteration, the smallest value and the current value swap their positions. To accomplish this, the algorithm uses nested loops to compare array elements.
As the length of the array increases to N, the time complexity would be O(N²) because we use two nested loops. The algorithm has a space complexity of O(1) as the sorting process doesn’t need an extra array to store the final result.
Best Case Complexity: it occurs when we need to sort a sorted array. The algorithm would need to perform comparisons without swapping values.
Average Case Complexity: this scenario occurs when a mix of both sorted and unsorted values needs to be sorted in ascending order. The algorithm would need to perform comparisons while swapping some values.
Worst Case Complexity: assuming we have a list of numbers that are in descending order and we need to sort them in ascending order, the algorithm would encounter a worst-case complexity as the length of that array grows to N. Therefore, the algorithm compares while swapping all the values.
Advantages of Using Selection Sort
Selection sort is ideal for sorting values that do not occupy a lot of memory. As the length of the array increases, the time taken to sort it increases exponentially as the algorithm has a time complexity of O(N²).
We can use this algorithm when the cost of swapping values doesn’t matter. For example, if the computing resources we need to swap those values are minimal, we could consider using this algorithm.
Ideal for situations where the cost of writing to a disk space matters. For example, a flash disk with no extra space could work with this algorithm as opposed to a sorting algorithm such as bubble sort that has a space complexity of O(N²).
Disadvantages of Using Selection Sort
We should not use selection sort in a sorted array, as it would still perform O(N²) comparisons. In such a scenario, a sorting algorithm such as bubble sort would perform those comparisons in one iteration.
Selection sort becomes inefficient as the size of the array grows. Using this algorithm in CPU-intensive applications could reduce their performance.
Selection Sort Algorithm Performance in C#
Let’s verify that the selection sort algorithm has a time complexity of O(N²) by using performance benchmarks to test how long the algorithm takes to sort an array.
To kickstart this process, we are going to define a method that generates random numbers and adds them to an array with a specific length:
public static int[] AddRandomElements(int size)
{
var array = new int[size];
var rand = new Random();
var maxNum = 10000;
for (int i = 0; i < size; i++)
array[i] = rand.Next(maxNum + 1);
return array;
}
The AddRandomElements method takes the length of the array as its input. Using the inbuilt Random class, we generate integer values (less than 10000) that we’re going to put into the array.
To simulate a scenario where we have an array that is in order, we are going to define a method AddSortedElements that generates a sequence of elements:
public static int[] AddSortedElements(int size)
{
var array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i;
return array;
}
Next, we are going to run a benchmark to understand how the algorithm performs when sorting arrays that have random elements:
int[] smallArray = AddRandomElements(200); int[] mediumArray = AddRandomElements(2000); int[] largeArray = AddRandomElements(200000);
We define three array objects of different sizes (to simulate time complexity scenarios) that hold random numbers from the AddRandomElements method. Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:
| Method | NumArray | Mean | Error | StdDev | |---------- |-------------- |-----------------:|-----------------:|-----------------:| | SortArray | Int32[200000] | 50,512,655.47 μs | 1,002,122.393 μs | 1,468,898.010 μs | | SortArray | Int32[2000] | 3,843.17 μs | 187.741 μs | 553.558 μs | | SortArray | Int32[200] | 40.56 μs | 1.775 μs | 5.232 μs |
We are going to assess whether the algorithm performs better when its attempts to sort arrays that are already in order than when it sorts arrays holding random elements. We invoke the AddSortedElements method when defining the array objects we are going to use for the next performance run:
int[] sortedSmallArray = AddSortedElements(200); int[] sortedMediumArray = AddSortedElements(2000); int[] sortedLargeArray = AddSortedElements(200000);
Let’s see if there is any performance improvement in this run:
| Method | NumArray | Mean | Error | StdDev | |---------- |-------------- |-----------------:|-----------------:|-----------------:| | SortArray | Int32[200000] | 46,223,271.04 μs | 1,505,138.836 μs | 4,414,311.658 μs | | SortArray | Int32[2000] | 3,565.99 μs | 132.440 μs | 390.502 μs | | SortArray | Int32[200] | 38.67 μs | 1.746 μs | 5.149 μs |
Although selection sort performs slightly better when dealing with sorted arrays, it performs poorly when compared to other sorting algorithms such as merge sort. The benchmark shows that the best, average, and worst complexity of the selection sort implementation is O(N²).
Conclusion
So, in this article, we’ve learned about the selection sort algorithm and its time and space complexity. We’ve covered how to implement the selection sort in C#, and also when should we use it and when not.
