Алгоритмы на JavaScript: пузырьковая сортировка

Здравствуйте, дорогие мои!

Как обещала, начинаем разбор популярных алгоритмов, которые задают на собеседовании. Несмотря на то, что мы фронтендеры с алгоритмами почти не работаем в силу специфики (по ним чаще всего гоняют бэков), но на собеседованиях, например в Яндексе, такие вещи все равно задают. И у нас на клиенте есть такие вещи, как поиски и сортировки.

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

В сети можно встретить массу примеров на Python. Особенности этой сортировки:

  1. Это почти самая долгая сортировка — для него характерна квадратичная сложность О(N2): чем больше массив, тем больше количество операций, которое понадобится для выполнения алгоритма.
  2. Цикл в цикле. Первый цикл — перебор по исходному массиву от первого элемента к последнему. Второй — перебор массива, который получился в результате предыдущей сортировки.
  3. Сравнивается по 2 соседних элемента массива. Если первый элемент больше второго, то они меняются местами. И так повторяется до тех пор, пока массив не будет отсортирован полностью.
  4. Условием выхода из цикла будет проход по массиву, в котором не было совершено ни одной перестановки элементов местами.

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

bubble-sort-array

 

Итак, функция пузырьковой сортировки массива на JavaScript будет выглядеть следующим образом:

  1. На вход функция принимает массив. Конечно, по-хорошему нужно проверить в функции, является ли переданный аргумент массивом и выкинуть exception, если было передано что-то другое. Но я не буду перегружать код и возьму упрощенный вариант.
  2. Как я уже говорила, будет иметь 2 цикла for (), вложенных в друг друга. Если array[j] больше, чем array[j + 1], то меняем их местами.
  3. В конце вернем отсортированный массив.

Имплементация алгоритма

function bubbleSort (arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 ; j++) {
            if (arr[j] > arr[j + 1]) {
                let swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
            }
        }
    }
    return arr;
}
bubbleSort([37, 45, 29, 8]);

Если мы запустим данный алгоритм в консоли браузера, то в конце получим массив [8, 29, 37, 45] и для сортировки 1000 элементов понадобится 7 ms.

Тестирование алгоритма

Проверим, корректно ли отработает написанный нами алгоритм на различных наборах данных.

Тест-кейс №1. Передадим в массиве последовательность чисел, одно из которых отрицательное число.

[37, 45, 29, 8, 12, 88, -3]

Сортировка сработала верно.

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Advertisment ad adsense adlogger