Selection Sort in C#

Selection sort is one of the basic algorithms for sorting data, its simplicity proves useful for sorting small amounts of data. Selection sort works by first starting at the beginning array (index 0) and traverses the entire array comparing each value with the current index, if it is smaller than the current index than that index is saved. Once the loop has traversed all the data and if a smaller value than the current index was found a swap is made between the current index in the index where the smaller value was found. The current index is then incremented, now to index 1, the algorithm repeats. Of course, a visual representation is usually more useful. Take an unsorted array that holds five integers.

There are three main variables in selection sort, the variable 'i' keeps the index that may be potentially switched if a smaller value is found. The variable 'j' traverses through the array searching for a value smaller than 'min'. The variable 'min' is the current smallest value in the array, it's updated only if a value smaller than it is found.

Since 'min' always recieves the value of index 'i' after every iteration, 'j' can begin one more than 'i'. If index 'j' started at index 'i' then 'min' would be comparted with itself obviously there is no need for that. In this algorithm there are two loops, the first loop containing the 'i' variable the second loop within the first loop contains the variable 'j'. For example.

for (int i=0; i < n-1; i++)
{
    for (int j=i+1; j < n; j++)
}
//where n is the number of elements inside the array

Animation of Selection Sort

The algorithm begins here
j++, min is updated since 1 < 2
j++, min isn't updated since 3 !< 1
j++, min isn't updated since 4 !< 1
j is done, index min switches with index i
i++,  j  =  i+1,  min = i
min is updated since 2 < 5
j++, min isn't updated since 3 !< 2
j++, min isn't updated since 4 !< 2
j is done, index min switches with index i i++,  j  =  i+1,  min = i
j++, min is updated since 3 < 5
j++, min isn't updated since 4 !< 3
j is done, index min switches with index i
i++,  j  =  i+1,  min = i
min is updated since 4 < 5
j is done, index min switches with index i
i++,  j  =  i+1,  min = i
The loop breaks since 'i' is no longer less than n-1, which in this case is 4. Notice why 'i' breaks at n-1 because once 'i' reaches the end of the array the data is already sorted so there is no need to continue. Now for the fun part, the source code.

Source Code of Selection Sort in C#

public void selectSort(int [] arr)
{
        //pos_min is short for position of min
        int pos_min,temp;
         
        for (int i=0; i < arr.Length-1; i++)
        {
            pos_min = i;//set pos_min to the current index of array
                
                for (int j=i+1; j < arr.Length; j++)
                {
                    if (arr[j] < arr[pos_min])
                    {
                        //pos_min will keep track of the index that min is in, this is needed when a swap happens
                        pos_min = j;
                    }                                          
                }
                
        //if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
        if (pos_min != i)
        {
            temp = arr[i];
            arr[i] = arr[pos_min];
            arr[pos_min] = temp;
        }
    }
}

Time Comlexity of Selection Sort

The time complexity of selection sort is O(n²), for best, average, and worst case scenarios. Because of this selection sort is a very ineffecient sorting algorithm for large amounts of data, it's sometimes preffered for very small amounts of data such as the example above. The complexity is O(n²) for all cases because of the way selection sort is designed to traverse the data. The outer loops first iteration has n comparisons (where n is the number of elements in the data) the second iteration would have n-1 comparisons followed by n-2, n-3, n-4...thus resulting in O(n²) time complexity.