Как устроен алгоритм сортировки пузырьком

На собеседованиях разработчиков очень часто просят рассказать, как устроен тот или иной алгоритм, как его реализовать и оптимизировать. Преподаватель программы JavaScript в Эльбрус Буткемп Юлия Тарасова на примере объясняет, как работает алгоритм сортировки пузырьком.

Алгоритм сортировки пузырьком позволяет выстроить данные в массиве в порядке убывания — от меньшего элемента к большего. Он берет два первых элемента массива, сравнивает их и расставляет по порядку. Следующим шагом алгоритм смещается на один элемент и сравнивает первый со вторым, третьим и так далее до конца массива.

Рассмотрим, как устроен этот процесс, на примере:

const test = [33, 245, 1, 15, 122, 5, 65, 90]
bubbleSort (test);

Это массив, элементы в котором расположены неупорядоченно. Сортировка пузырьком будет сравнивать первый элемент со вторым, третьим и так далее до конца массива. Если первый элемент будет больше следующего (например, 33 больше 1, 15 и 5), они поменяются местами. Так сравниваются все элементы в массиве, пока они не выстраиваются в нужном порядке, от 1 до 245.

Суть алгоритма в том, что самый большой пузырек (элемент) всплывает наверх, а остальные выстраиваются вслед за ним.

Теперь попробуем реализовать алгоритм: напишем функцию bubbleSort, которая принимает массив и проходит по нему циклом от нулевого до последнего элемента.

function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i ++) {
    for (let j = 0; j < arr.length; j ++)
      if (arr [j] > arr [j + 1] {
      const tmp = arr [j]
      arr [j] = arr [j + 1]
      arr [j +1] > tmp 
    }
  }
 }
console.log (arr);
}

Одного прохода по массиву будет недостаточно, потому что он не успеет сортировать.  Поэтому напишем цикл в цикле, который будет проверять, что если текущий элемент  больше следующего (j + 1), их нужно поменять их местами.

if (arr [j] > arr [j + 1]
arr [j] = arr [j + 1]
arr [j +1] > arr [j] 

Важно отметить, что такая реализация может существовать только в качестве примере. На практике обычно создается временная переменная, которая сохраняет предыдущее значение: const tmp = arr [j].

Теперь в цикле можно присвоить arr [j +1] не сохраненное значение, а значение временной переменной:

const tmp = arr [j]
arr [j] = arr [j + 1]
arr [j +1] > tmp

Теперь добавим console.log и посмотрим на результат работы алгоритма в терминале:

Следующим шагом можно оптимизировать код. Чтобы понять, какие требуют доработки, выведем в консоль arr [j +1] на каждом шаге:

function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i ++) {
    for (let j = 0; j < arr.length; j ++)
    console.log (arr [j + 1])
  }
console.log (arr);
}

При запуске в терминале появится несколько undefined. Когда внутренний цикл проходит по длине массива и доходит до конца, arr [j + 1] становится undefined, поскольку выходит за пределы массива. Поэтому в цикле стоит указать, что нужно проходить на один элемент меньше:

function bubbleSort(arr) {
  // Запоминаем длину массива
  const len = arr.length;

  // Проходим по массиву len - 1 раз
  for (let i = 0; i < len - 1; i++) {
    // В каждой итерации сравниваем j-й элемент со следующим
    for (let j = 0; j < len - i - 1; j++) {
      // Если j-й элемент больше следующего, меняем их местами
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  // Возвращаем отсортированный массив
  return arr;
}

Теперь в терминале нет ни одного undefined, однако в коде еще есть проблемы. Он не эффективен, поскольку цикл проходит по одним и тем же элементам несколько раз.

Для того, чтобы исправить этот недостаток, ограничим внутренний цикл: добавим вычитание индекса элемента, по которому цикл уже прошел:

function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1 - i; i ++) {
    for (let j = 0; j < arr.length; j ++)
 if (arr [j] > arr [j + 1] {
         const tmp = arr [j]
         arr [j] = arr [j + 1] 
         arr [j +1] > tmp
      }
    }

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

function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1 - i; i ++) {
    for (let j = 0; j < arr.length; j ++)
 if (arr [j] > arr [j + 1] {
         const tmp = arr [j]
         arr [j] = arr [j + 1] 
         arr [j +1] > tmp
      }
    }

После этого проверим, что оптимизация ничего не сломала: запустим код и посмотрим на его вывод.