Сортировка пузырьком, JavaScript

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

Сортировку пузырьком (Bubble Sort) также иногда называют сортировкой простыми обменами.

В общем-то единственным преимуществом этого алгоритма и является то, что он предельно прост в реализации. Сам по себе он не является эффективным, имеет сложность O(n²) и на практике не используется. Но знать его не помешает, ведь на его основе созданы другие более сложные и оптимизированные алгоритмы — сортировка перемешиванием (Cocktail sort), сортировка кучей (Heapsort), быстрая сортировка (Quicksort).

Суть алгоритма в сравнении пары соседних элементов — если они стоят в неправильном порядке, то их меняют местами. Чтобы отсортировать таким образом весь массив длиной N, придется пройтись по нему N-1 раз (последний элемент уже будет отсортирован на предыдущей итерации, поэтому для него проход не требуется). Также за каждый проход в конец массива “всплывает” при сортировке по возрастанию — наибольшее число, по убыванию — наименьшее. А значит на следующей итерации его можно уже не проверять.

Визуализация алгоритма сортировки пузырьком

В первом приближении алгоритм для сортировки по возрастанию выглядит так:

function bubbleSort(arr) {
    for (var i = 0, endI = arr.length - 1; i < endI; i++) {
        for (var j = 0, endJ = endI - i; j < endJ; j++) {
            if (arr[j] > arr[j + 1]) {
                var swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
            }
        }
    }
    return arr;
}

Но в таком виде никак не учитывается какой массив поступил на вход и даже для уже отсортированного массива программа должна будет выполнить все итерации циклов.

Ее можно оптимизировать добавив флаг, отслеживающий перестановку элементов — если за очередной проход по массиву не произошло ни одной, значит массив уже отсортирован. Код теперь будет выглядеть так:

function bubbleSort(arr) {
    for (var i = 0, endI = arr.length - 1; i < endI; i++) {
        var wasSwap = false;
        for (var j = 0, endJ = endI - i; j < endJ; j++) {
            if (arr[j] > arr[j + 1]) {
                var swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
                wasSwap = true;
            }
        }
        if (!wasSwap) break;
    }
    return arr;
}

Ну и напоследок перепишем наш алгоритм на новый синтаксис ES6 и избавимся от дополнительной переменной:

const bubbleSort = arr => {
    for (let i = 0, endI = arr.length - 1; i < endI; i++) {
        let wasSwap = false;
        for (let j = 0, endJ = endI - i; j < endJ; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                wasSwap = true;
            }
        }
        if (!wasSwap) break;
    }
    return arr;
};

Если у вас возникли трудности с понимаем работы алгоритма, можно посмотреть его визуализацию на видео:

Надеюсь у вас не осталось вопросов :)
Но если остались — добро пожаловать в комментарии.

P. S. Все мы люди :) А значит нам свойственно ошибаться.
Увидели опечатку или ошибку — выделите текст, кликните в сплывающем меню иконку сообщения с замочком и напишите о ней.
Я буду вам очень признательна.