Selection Sort is a simple comparison-based sorting algorithm that divides the input list into two parts: a sorted subarray and an unsorted subarray. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted subarray and swaps it with the first unsorted element, expanding the sorted subarray.

Basic Implementation

function selectionSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    // Find the index of the minimum element in the unsorted part
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // Swap the found minimum element with the first unsorted element
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

How Selection Sort Works

• The algorithm starts with the entire array considered as an unsorted subarray.

• It iterates through the unsorted subarray to find the index of the minimum element.

• The minimum element is then swapped with the first unsorted element, effectively adding it to the sorted subarray.

• The process is repeated, with the sorted subarray growing and the unsorted subarray shrinking until the entire array is sorted.

Time Complexity

The time complexity of Selection Sort is O(n^2), where 'n' is the number of elements in the array. This is because, in each iteration, the algorithm performs a nested loop to find the minimum element in the unsorted subarray.

Space Complexity

Selection Sort has a space complexity of O(1) since it only uses a constant amount of additional memory for variables like minIndex.

Advantages of Selection Sort

Simplicity

Selection Sort is easy to understand and implement, making it suitable for educational purposes.

In-Place Sorting

The algorithm sorts the array in-place, meaning it doesn't require additional memory for a separate data structure.

Limitations of Selection Sort

Selection Sort's quadratic time complexity makes it inefficient for large datasets. More advanced sorting algorithms like QuickSort or MergeSort are preferred for larger datasets.

When to Use Selection Sort

Selection Sort is suitable for small datasets or scenarios where simplicity is more critical than efficiency. In practical applications, it is often outperformed by other sorting algorithms for larger datasets.

Conclusion

While Selection Sort may not be the most efficient sorting algorithm, understanding its principles is valuable for learning about sorting techniques and algorithms in general. It provides a straightforward introduction to the concept of in-place sorting and the selection of elements in an array based on comparisons.