Selection sort

Easy TimeO(n²) SpaceO(1)

Given an array arr of numbers, sort it into ascending order in place by filling each position in turn with the smallest value still unplaced. Each position is written at most once, and the number of comparisons is the same whatever order the input arrives in.

Examples

Example 1

Input
arr = [5, 2, 8, 1, 4]
Output
[1,2,4,5,8]
The same five values, ascending.

Example 2

Input
arr = [1, 2, 3, 4]
Output
[1,2,3,4]
Already sorted, and it still makes all 6 comparisons to establish it.

The Code

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    if (min !== i) {
      const tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
  return arr;
}
selectionSort([5, 2, 8, 1, 4]);
Done

The first 18 calls, of 20. This one does not fit on a page.

Step through selectionSort([5, 2, 8, 1, 4]) call by call

More like this

All sorting examples (8) →