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

На собеседованиях разработчиков очень часто просят рассказать, как устроен тот или иной алгоритм, как его реализовать и оптимизировать. Преподаватель программы JavaScript в Elbrus Bootcamp Юлия Тарасова на примере объясняет, как работает алгоритм сортировки пузырьком.
Алгоритм сортировки пузырьком позволяет выстроить данные в массиве в порядке убывания — от меньшего элемента к большего. Он берет два первых элемента массива, сравнивает их и расставляет по порядку. Следующим шагом алгоритм смещается на один элемент и сравнивает первый со вторым, третьим и так далее до конца массива.
Рассмотрим, как устроен этот процесс, на примере:
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) {
for (let i = 0; i < arr.length - 1; i ++) {
for (let j = 0; j < arr.length; j ++)
console.log (arr [j + 1])
}
console.log (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
}
}
После этого проверим, что оптимизация ничего не сломала: запустим код и посмотрим на его вывод.