JavaScript algorithm: selection sort

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

You can have an array of objects, and you can compare object properties, such as sorting by age or alphabetically by last name. The details have not changed.

We work this way: we choose the first project. Then, we compare it with the second item. If the second term is smaller, we swap it with the first term. And so on, we compare the first project withEveryThe items in the array.

After knowing the smallest item, we switch to the second element and then compare it withEveryItems in the array, ignore index 0, because we already know that this is the minimum value. And so on, until the end of the array.

As you can see, this algorithm is very expensive. It not only iterates over each item in the array: for each item, it iterates over the array again.

Its complexity isO(n^2). Please note that technically, the number of items we compare has been decreasing, but this does not mean anything for the complexity of the Big O convention.

This is our realizationSelect 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]

Download mine for freeJavaScript beginner's manual


More js tutorials: