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# using a .NET (Core) console application.

To download the source code for this article, you can visit our GitHub repository.

Let’s start. 

What Is Selection Sort?

The goal of the selection sort algorithm is to find the minimum value of an array through iterations. For each iteration, the algorithm compares the current value of the array with the current minimum value. If the current value is smaller than the minimum value, the positions of these values are swapped. This process continues until the sorting process is complete. 

Let’s learn how selection sort in C# works and understand its time complexity. 

Selection Sort Algorithm

Let’s assume we have an array of five numbers we need to sort in ascending order:
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:
array[] = 10, 40, 20, 30, 50

Then, we check the elements 1 to 4 and place the smallest value at position 1. In this case, 20 is the minimum and we swap it with 40:
array[] = 10, 20, 40, 30, 50

Next, we check positions 2 through 4 and set the minimum value (30) to position 2:
array[] = 10, 20, 30, 40, 50

Time and Space Complexity

For each iteration, the smallest value and the current value swap their positions. Therefore, when implementing the selection sort algorithm, nested loops will come in handy when performing value comparisons: 

//outer loop iterates through the array
for (int i = 0; i < arrayLength - 1; i++)
{
    //set the smallest value to the current element
    //check for the smallest value and swap it with the current smallest element
    for (int j = i + 1; j < arrayLength; j++)
    {
        //determine the position of the smallest element
    }
    //swap the current element with the smallest value   
}

As the length of the array increases to N, the time complexity would be O(N²). 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.

Let’s learn how to implement Selection Sort in C# using a simple console application. 

Implementing Selection Sort in C#

First, let’s define a PrintArray method that would take an integer array and its length as parameters and print its values:

static void PrintArray(int[] numArray, int length) 
{
    for (int i = 0; i < length; i++)
    {
        Console.Write(numArray[i] + " ");
    }
}

As our next step, in the Main method, we are going to define an array that will undergo the sorting process and set its length using the Array.Length property:

int[] numArray = new int[10] { 57, 1, 98, 65, 88, 24, 45, 13, 79, 34 };
int arrayLength = numArray.Length;

To continue, let’s create a SortArray method that takes numArray and its length as parameters and sorts it:

static int[] SortArray(int[] numArray, int arrayLength) 
{
    int tempVar, smallestVal;

    for (int i = 0; i < arrayLength - 1; i++)
    {
        smallestVal = i;
        for (int j = i + 1; j < arrayLength; j++)
        {
            if (numArray[j] < numArray[smallestVal])
            {
                smallestVal = j;
            }
        }
        tempVar = numArray[smallestVal];
        numArray[smallestVal] = numArray[i];
        numArray[i] = tempVar;
    }
    return numArray;
}

The sorting process begins by defining 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, the elements are swapped. This process stops when the outer loop hits its arrayLength limit.  

Next, we are going to piece everything together calling SortArray and PrintArray to sort and display the values of numArray to the user:

public static void Main(string[] args) 
{ 
    int[] numArray = new int[10] { 57, 1, 98, 65, 88, 24, 45, 13, 79, 34 }; 
    int arrayLength = numArray.Length; 
    Console.Write("Unsorted array is: "); 
    PrintArray(numArray, arrayLength); 

    int[] sortedArray = SortArray(numArray, arrayLength); 
    Console.WriteLine(); 
    Console.Write("Sorted array is: "); 
    PrintArray(sortedArray, arrayLength); 
}

The program displays two values with one showing the unsorted array and the other showing its sorted variant:

Unsorted array is: 57, 1, 98, 65, 88, 24, 45, 13, 79, 34
Sorted array is: 1, 13, 24, 34, 45, 57, 65, 79, 88, 98

When Should We Use It?

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²).

When Should We Not Use It?

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. 

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.