MV's blog

Selection Sort

Selection sort is an elementary sort that works by finding the minimum/maximum - depeneding on sorting direction in the [`i-th

• 1,array.length] interval andswapping itwith thei-th element. By doing this theelementsfrom the0-thtoi-th - 1element arealways sorted`.

Time complexity

Selection sort uses (N-1) + (N-2) + (N-3) + ... + 1 + 1 ~ N2/2 compares and N exchanges. It is also insensitive to input, i.e its running time will be quadratic even if the input is sorted.

Sample typescript implementation for sorting numbers in ascending order.

function selectionSort(numbers: number[]): void {
  for (let i = 0; i < numbers.length; i++) {
    let minIndex = i;

    // Find the minimum from the ith + 1 element
    // because the elements from 0 to i-th - 1 are always sorted
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[j] < numbers[minIndex]) {
        minIndex = j;
      }
    }

    // Replace it with the i-th element
    let tmp = numbers[minIndex];
    numbers[minIndex] = numbers[i];
    numbers[i] = tmp;
  }
}