Selection Sort

Selection Sort is a straightforward sorting algorithm based on in-place comparison, that is, it works by repeatedly finding the minimum element from the unsorted part of the list and placing it at the beginning.

How it works

Suppose we have an array of n unsorted numbers. The algorithm works as follows:

1. Starting from index 0, it searches for the minimum value in the array.
2. Once the minimum is found, it swaps it with the element at the starting index.
3. It moves to the next index and repeats the process for the remaining subarray.
4. This process is repeated until all elements in the array are sorted.

These steps are performed repeatedly until the entire array is sorted.

Here is a simple implementation in C#:

public void SelectionSort(int[] arr)
{
    var len = arr.Length;

    for (var i = 0; i < len - 1; i++)
    {
        var minIndex = i;

        for (var j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }

        (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

Time complexity

In the worst, average and best case, the time complexity is O(n²), where n is the number of elements to be sorted. This is because the algorithm performs a number of comparisons proportional to the square of the number of elements, irrespective of their initial arrangement.

Space complexity

Since this is an in-place sorting algorithm, thus requiring no additional space to sort a collection, the space complexity is O(1), making it a good choice for situations where memory usage is a crucial factor.

Conclusion

Selection Sort is not a particularly efficient sorting algorithm for large data sets, yet it provides a solid foundation for understanding more complex sorting algorithms. Its simplicity makes it an excellent teaching tool for computer science students and anyone new to the world of sorting algorithms.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)