В этом посте мы рассмотрим пару алгоритмов сортировки массивов в JavaScript и покажем их базовую реализацию. Оставайтесь с нами во второй части, где мы рассмотрим варианты оптимизации для каждого из них. (Этот пост также скоро будет расширен, чтобы включить остальные наиболее распространенные алгоритмы сортировки: сортировка вставками, сортировка слиянием, быстрая сортировка и сортировка по основанию)

Пузырьковая сортировка

Пузырьковая сортировка — худший алгоритм сортировки, который только можно придумать. Есть люди, активно пытающиеся исключить его из учебных программ по информатике из-за его сложности O(n²). Хотя, возможно, нет необходимости показывать кому-то, как сделать что-то наихудшим способом, когда есть гораздо более эффективные альтернативы, я считаю, что это все же хороший образовательный инструмент для обучения новичков работе алгоритмов из-за его простоты. Кроме того, если список уже в основном отсортирован, пузырьковая сортировка не такая уж плохая идея.

Название происходит от больших значений (или меньших, в зависимости от того, как вы сортируете), которые «всплывают» до конца массива. Как это работает, вы перебираете массив и меняете местами каждые два соседних элемента, если они не отсортированы. Цикл, выполняющий такую ​​задачу, вложен во внешний цикл, также равный количеству элементов, поэтому выполняется обход массива n раз, в результате чего при каждом запуске наибольшие числа будут сдвигаться вверх ближе к концу. . так:

[2,5, 4,3,1]

Сначала мы смотрим на 2 и 5, которые уже отсортированы. Затем мы переходим к 5 и 4, которых нет, поэтому мы меняем их местами.

[2,4,5,3,1]

затем мы смотрим на 5 и 3, которые не отсортированы, поэтому они меняются местами.

[2,4,3,5,1]

наконец, мы смотрим на 5 и 1 и меняем их местами.

[2,4,3,1,5]

Внутренний цикл выполнен, поэтому мы возвращаемся ко второй итерации внешнего цикла, в результате чего 4 будет слева от 5;

[2,3,1,4,5]

Как только мы запустим внутренний цикл 5 раз, массив будет отсортирован.

[1,2,3,4,5]

Вот как это выглядит в коде:

function  bubbleSort(array) {
let j = 0;
while (j <= array.length) {
  for (i = 0; i < array.length; i++) {
    if (array[i] > array[i + 1]) {
      let hold = array[i];
      array[i] = array[i + 1];
      array[i + 1] = hold;
    }
  }
j++;
}
return array;
};

Сортировка выбором

Сортировка выбором чем-то похожа на сортировку пузырьком. Вместо того, чтобы перемещать большие элементы в конец массива, мы перемещаем меньшие элементы влево от массива. Реализация несколько другая. Для каждой итерации мы ищем наименьший текущий элемент и перемещаем его в соответствующую позицию. Однако нам также нужен вложенный цикл внутри внешнего цикла. Мы начнем со сравнения первых двух элементов и сохраним наименьший из двух, затем мы сравним сохраненный элемент с каждым другим значением, и если мы обнаружим, что есть меньший элемент, мы заменим его текущим сохраненным значением. В конце прохода мы меняем местами наименьший найденный элемент с элементом в первой позиции.

Теперь для второй итерации мы начинаем со второй позиции, так как мы уже отсортировали элемент в первую позицию, третий проход начнется с третьего элемента и так далее и тому подобное. Итак, резюмируем: мы сохраняем первый элемент как наименьшее значение, которое вы видели, сравнивайте указанное значение со следующим элементом, пока не найдете меньшее и не достигнете конца массива. Мы сохраняем индекс, а не само значение, поэтому мы можем поменять его местами с крайним левым элементом, если значение с индексом 0 еще не было наименьшим. Повторите процесс, начиная с несортированного индекса, убедитесь, что вы не начинаете с любого места в уже отсортированном подмассиве, иначе вы всегда найдете один и тот же минимум. Для этого инициализация внутреннего цикла может быть j = i + 1;

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

[2,5,4,3,1]

Мы устанавливаем наименьшее значение = 2, так как это первое число, которое мы видим. Затем мы сравниваем его со следующим элементом. 5 определенно не меньше, ни 4, ни 3, но в конце концов мы находим меньший, 1. Поэтому мы меняем их местами.

[1,5,4,3,2]

Теперь для следующей итерации мы начинаем со второй позиции индекса и устанавливаем 5 как наименьшее число, так как это первое, с которым мы столкнулись. При сравнении с остальными числами мы обнаруживаем, что два на самом деле наименьшее число, поэтому мы меняем его на 5.

[1,2,4,3,5]

Теперь мы устанавливаем 4 наименьшее число, так как мы уже отсортировали первые два элемента. Вот 3 — наименьший в несортированном наборе, поэтому мы меняем его местами.

[1,2,3,4,5]

Ух ты! мы закончили раньше! несмотря на то, что осталась еще одна итерация, алгоритм обнаруживает, что менять местами нечего, и возвращает наш отсортированный массив.

Вот как выглядит код:

function selectionSort(){
for (let i = 0; i < array.length; i++){
    let lowest = i;
    for(let j = i + 1; j < array.length; j++){
      if(array[j] < array[lowest]){
         lowest = j;
      }
    }
    if (i !== lowest){
      let hold = array[i];
      let array[i] = array[lowest];
      let array[lowest] = hold
    }
 }
  return array;
}