Time and Space Complexity of Selection Sort

Selection sort is a simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted part of the list and swaps it with the first unsorted element.

def selection_sort(arr):
    n = len(arr)

    # Loop through each element in the array
    for i in range(n):
        # Assume the current element is the minimum
        min_idx = i

        # Find the index of the smallest element
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j  # Update the index

        # Swap the current element with the smallest element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    # Return the sorted array
    return arr

template<typename T>
void selection_sort(std::vector<T>& arr) {
    int n = arr.size();

    // Loop through each element in the array.
    for(int i = 0; i < n; ++i) {
        // Assume the current element is the minimum.
        int min_idx = i;

        // Find the index of the smallest element
        for(int j = i + 1; j < n; ++j) {
            if(arr[j] < arr[min_idx]) {
                min_idx = j;  // Update the index
            }
        }

        // Perform the swap between the current element 
        // and the minimum element
        std::swap(arr[i], arr[min_idx]);
    }
}

Time Complexity: <katex>O(n^{2})</katex>

Selection sort has a time complexity of <katex>O(n^{2})</katex> in all cases.

It's because it repeatedly selects the minimum (or maximum) element from the unsorted portion of the array and swaps it into its correct position. For example,

5, 2, 9, 1, 5, 6

Steps:

Thus, the total comparisons is:

n + (n-1) + (n-2) + ... + 1 = O(n^2)

Therefore, the time complexity of the selection sort is <katex>O(n^{2})</katex>.

When to Use Selection Sort?

Selection sort is a memory-efficient algorithm with a space complexity of O(1), making it suitable for limited memory environments.

However, its quadratic time complexity <katex>O(n^{2})</katex> makes it inefficient for large datasets.

When to Use:

1. Small Datasets: With fewer elements, the number of comparisons and swaps remains manageable.
2. Memory Constraints: Selection sort's low memory usage makes it favorable when you have limited memory.

When to Avoid:

1. Large Datasets: Its inefficient time complexity makes algorithms like Merge Sort or Quick Sort more suitable.