JavaScript Algorithms: Selection Sort

Selection sort sorts an array by repeatedly finding the smallest remaining item and moving it into place. It’s one of the first sorting algorithms you learn, because the idea maps directly to how you’d sort things by hand.

Suppose we have an array of numbers, and we want to sort it by element size.

You could have an array of objects, and you could compare an object property, like sorting by age, or alphabetically by last name. The details don’t change.

How the algorithm works

We work in this way: we pick the first item. Then we compare it with the second item. If the second item is smaller, we remember its position. And so on, we compare against every item in the array, and at the end we swap the smallest one into the first position.

Once we know we have the smallest item at index 0, we switch to the second element, and we compare it with every remaining item, ignoring index 0, since we already know that’s the minimum. And so on, until the end of the array.

Take [38, 5, 27, 12]. The first pass finds 5 and swaps it with 38, giving [5, 38, 27, 12]. The second pass finds 12 and swaps it with 38: [5, 12, 27, 38]. The third pass finds 27 already in place, and we’re done.

As you can see, the algorithm is very expensive. It not only iterates on every item of the array: for each item, it iterates again the array.

Its complexity is O(n^2). Note that technically the number of items we compare keeps becoming smaller, but this does not mean anything in terms of the Big O conventions for complexity.

The implementation

Here’s our implementation of selection sort.

const selectionSort = (originalList) => {
  //we first copy the array to avoid modifying the original array, since objects are passed by reference in JS
  const list = [...originalList]
  const len = list.length
  for (let i = 0; i < len; i++) {
    let min = i
    for (let j = i + 1; j < len; j++) {
      if (list[min] > list[j]) {
        min = j
      }
    }
    if (min !== i) {
      // a new minimum is found. Swap that with the current element
      ;[list[i], list[min]] = [list[min], list[i]]
    }
  }
  return list
}

const listOfNumbers = [1, 6, 3, 4, 5]
console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

Notice the semicolon before the swap line. Since we write JavaScript without semicolons, a line starting with [ gets glued to the previous line by the parser, and you get a runtime error. That leading ; prevents it. This is one of the very few cases where you need it.

When would you use it?

Almost never in real code. For anything practical, Array.prototype.sort() is faster and already there.

Selection sort is worth knowing because it’s easy to reason about, and it makes few swaps: at most one per pass. But for large arrays the O(n^2) comparisons dominate, and algorithms like merge sort or quicksort win by a huge margin.