← flaviocopes.com

JavaScript Algorithms: Selection Sort

Published Nov 22 2020

Psssst! The 2023 WEB DEVELOPMENT BOOTCAMP is starting on FEBRUARY 01, 2023! SIGNUPS ARE NOW OPEN to this 10-weeks cohort course. Learn the fundamentals, HTML, CSS, JS, Tailwind, React, Next.js and much more! ✨

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]


I write books for developers 👇🏼

© 2023 Flavio Copes Flavio Copes made in Italy 🇮🇹 using Notion to Site Notion to Site