JavaScript Algorithms: Selection Sort

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.

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 swap it with the first. And so on, we compare this first item with every item in the array.

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

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.

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]