Алгоритмы JavaScript: Сортировка выбора

Предположим, у нас есть массив чисел, и мы хотим отсортировать его по размеру элемента.

У вас может быть массив объектов, и вы можете сравнить свойство объекта, например, отсортировать по возрасту или в алфавитном порядке по фамилии. Детали не меняются.

Мы работаем таким образом: мы выбираем первый товар. Затем мы сравниваем его со вторым пунктом. Если второй предмет меньше, мы меняем его местами с первым. И так далее, мы сравниваем этот первый элемент с каждым элементом в массиве.

Как только мы узнаем, что у нас есть наименьший элемент, мы переключаемся на второй элемент и сравниваем его с каждым элементом в массиве, игнорируя индекс 0, так как мы уже знаем, что это минимум. И так далее, до конца массива.

Как вы можете видеть, алгоритм очень дорогой. Он не только выполняет итерацию по каждому элементу массива: для каждого элемента он снова выполняет итерацию массива.

Его сложность составляет O(n^2) . Обратите внимание, что технически количество сравниваемых элементов продолжает уменьшаться, но это ничего не значит с точки зрения соглашений Big O для сложности.

Вот наша реализация сортировка по выбору .

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]

Оригинал: “https://flaviocopes.com/selection-sort-javascript/”