How Selection Sort Works

Selection Sort is a simple comparison-based sorting algorithm. It works by repeatedly selecting the smallest (or largest, depending on the sorting order) element from the unsorted portion of the list and swapping it with the first unsorted element. This process is repeated until the entire list is sorted.

Algorithm

1. Start with the first element of the array as the minimum.
2. Compare the minimum with the rest of the elements in the array to find the smallest element.
3. If a smaller element is found, Swap it with the first element of the unsorted portion of the array.
4. Move the pointer to the next element and repeat the process until the entire array is sorted.

    // Javascript
    selectionSort(nums) {
        for(let i = 0; i<nums.length; i++){
            let min = i; // assume the current element is the minimum
            for(let j = i+1; j<nums.length; j++){
                if(nums[j] < nums[min]){
                    // update the minimum index if a smaller element is found
                    min = j;
                }
            }
            // swap the minimum element with the first unsorted element
            [nums[i], nums[min]] = [nums[min], nums[i]];
        }
        return nums;
    }

    # Python
    def selection_sort(nums):
        for i in range(len(nums)):
            min_index = i  # assume the current element is the minimum
            for j in range(i+1, len(nums)):
                if nums[j] < nums[min_index]:
                    # update the minimum index if a smaller element is found
                    min_index = j
            # swap the minimum element with the first unsorted element
            nums[i], nums[min_index] = nums[min_index], nums[i]
        return nums

Time and Space Complexity

The time complexity of Selection Sort is O(n^2) in all cases (best, average, and worst) because it requires two nested loops to complete the sorting process.

The outer loop runs n times, and the inner loop also runs n times in each iteration of the outer loop, leading to n * n = n^2 comparisons. In case of already sorted array, it still requires n^2 comparisions.

The space complexity of Selection Sort is O(1) because it is an in-place sorting algorithm.

Use case

Selection Sort is not the most efficient sorting algorithm for large datasets, but it can be useful in certain scenarios:

• When memory space is limited, as it is an in-place sorting algorithm.
• When the cost of swapping elements is high. Selection Sort minimizes the number of swaps by only swapping once per iteration of the outer loop.