Алгоритмы Javascript - пузырьковая сортировка
Следующий алгоритм в серии алгоритмов Javascript - пузырьковая сортировка. Как и сортировка вставкой, пузырьковая сортировка является алгоритмом сравнения и выполняется за время O (n²), что делает ее неэффективным алгоритмом для больших списков. Как мы видели в предыдущем посте о сортировке вставкой, часто на практике алгоритмы квадратичной сортировки превосходят более сложные алгоритмы в очень маленьких списках. Пузырьковая сортировка, по-прежнему придерживаясь этого принципа, неэффективна даже для небольших входных данных по сравнению с сортировкой вставкой. Скорее всего, вы никогда не реализуете пузырьковую сортировку на практике, но все же может оказаться полезным знать. В лучшем случае время выполнения - O (n) или линейное, что происходит, если входной массив уже отсортирован. В среднем время выполнения пузырьковой сортировки по-прежнему квадратично.
Идея пузырьковой сортировки заключается в том, что сравнивается каждая пара соседних значений, а затем эти два значения меняются местами, если первое значение больше второго. Таким образом, во время каждого прохода по массиву наибольшее значение «всплывает» вверх, а после каждого прохода наиболее правые элементы располагаются в правильном порядке. Вот пример: для массива [5,3,1,4,6] мы можем использовать пузырьковую сортировку для сортировки массива в порядке возрастания. Он начнется со сравнения первой пары значений, 5 и 3. 3 меньше 5, поэтому он поменяет два значения местами, а затем перейдет к сравнению следующей пары значений, 5 и 1. Он продолжится. делать это снова и снова, пока массив не будет отсортирован:
Итерация 1: [5,3, 1,4,6] → [3 , 5,1, 4,6] → [3,1, 5 , 4, 6] → [3,1,4, 5,6] → [3,1,4,5,6]
Итерация 2: [3,1, 4,5,6] → [1, 3,4, 5,6] → [1,3, 4 , 5, 6] → [1,3,4, 5,6] → [1,3,4,5,6]
Итерация 3: [1,3, 4,5,6] → [1, 3,4, 5,6] → [1,3, 4 , 5, 6] → [1,3,4, 5,6] → [1,3,4,5,6]
Как видите, после второй итерации массив уже отсортирован. Однако для пузырьковой сортировки требуется последний проход через массив, чтобы гарантировать, что никакие другие перестановки не требуются перед возвратом массива. Вот один из способов кодирования пузырьковой сортировки:
let bubbleSort = (inputArr) => {
let len = inputArr.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (inputArr[j] > inputArr[j + 1]) {
let tmp = inputArr[j];
inputArr[j] = inputArr[j + 1];
inputArr[j + 1] = tmp;
}
}
}
return inputArr;
};
В приведенной выше реализации код будет выполняться до тех пор, пока переменная «i» не станет равной переменной «len», что означает, что он может выполняться в уже отсортированном массиве более одного раза. Еще один немного более эффективный способ кодирования пузырьковой сортировки, который немного более эффективен, - это отслеживать переменную «swapped», для которой изначально установлено значение false. Во время каждой итерации, если значения меняются местами, для переменной «swapped» устанавливается значение true. Затем, используя цикл do-while, он будет запускать код только в том случае, если переменная подкачки истинна, тем самым гарантируя, что произойдет только 1 дополнительная итерация проверки. Код для этого выглядит так:
let bubbleSort = (inputArr) => {
let len = inputArr.length;
let swapped;
do {
swapped = false;
for (let i = 0; i < len; i++) {
if (inputArr[i] > inputArr[i + 1]) {
let tmp = inputArr[i];
inputArr[i] = inputArr[i + 1];
inputArr[i + 1] = tmp;
swapped = true;
}
}
} while (swapped);
return inputArr;
};
Вот и все для пузырьковой сортировки! Не стесняйтесь копировать и вставлять этот код в консоль своего браузера, чтобы увидеть, как он работает! Вы также можете добавить несколько операторов console.log в блок if, чтобы увидеть, как массив выглядит после каждой итерации при сортировке (осторожно, так как это приведет к спаму вашей консоли). Вы также можете прочитать мой пост о сортировке вставками, чтобы узнать больше об этом более полезном алгоритме. Спасибо за прочтение!
