Алгоритм пузырьковой сортировки никак не следит за текущим состоянием массива.
Даже если на вход мы отправим уже отсортированный массив, нам нужно будет столько же итераций цикла, как и для неотсортированного массива, чтобы получить результат.
Оптимизация сортировки пузырьком
Быстродействие пузырьковой сортировки в JavaScript можно улучшить, если добавить флаг (логическую переменную) который будет следить за тем был ли хотя бы один обмен на текущей итерации.
Если нет, то массив отсортирован и задача выполнена.
Чтобы убедиться в уменьшении количества итераций алгоритма, добавим счетчик outerLoopIterationCount. Будем увеличивать его на каждом проходе внешнего цикла и возвращать когда массив окажется отсортирован.
const optimizedBubbleSort = (arr) => {
let hasSwapped = false;
let outerLoopIterationCount = 0;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
hasSwapped = true;
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (!hasSwapped) {
return outerLoopIterationCount;
} else {
hasSwapped = false;
}
outerLoopIterationCount++;
}
return outerLoopIterationCount;
}
Для проверки возьмем два массива. Второй в два раза длиннее, но в нем всего лишь один элемент не на своем месте.
- выводим на экран начальное состояние массивов
- сортируем их и сохраняем количество итераций, которое вернет функция сортировки
optimizedBubbleSort - выводим на экран массивы еще раз, чтобы убедиться в том, что они отсортированы и проверить количество итераций, которое понадобилось для сортировки
const testData = [ 0, -1, 4, 5, 2, -3 ];
const almostSortedTestData = [ 12, -3, -1, 0, 2, 4, 5, 7, 8, 9, 10 ];
console.log(testData, `Initial testData state`);
console.log(almostSortedTestData, `Initial almostSortedTestData state`);
const iterationsTestData = optimizedBubbleSort(testData);
const iterationsAlmostSortedTestData = optimizedBubbleSort(almostSortedTestData);
console.log(testData, `Total iterations: ${iterationsTestData}`);
console.log(almostSortedTestData, `Total iterations: ${iterationsAlmostSortedTestData}`);
В консоли увидим такой результат:
[ 0, -1, 4, 5, 2, -3 ] Initial testData state
[ 12, -3, -1, 0, 2, 4, 5, 7, 8, 9, 10 ] Initial almostSortedTestData state
[ -3, -1, 0, 2, 4, 5 ] Total iterations: 6
[ -3, -1, 0, 2, 4, 5, 7, 8, 9, 10, 12 ] Total iterations: 2
Хотя второй массив и оказался в 2 раза длиннее, нам нужно было всего две итерации внешнего цикла, чтобы отсортировать его. Уже на втором проходе, флаг hasSwapped не изменился. Это значит, что обменов не было и массив уже отсортирован. Мы сразу же завершили алгоритм улучшенной сортировки пузырьком и не тратили лишнее время.
Кстати, если мы попробуем с помощью функции optimizedBubbleSort отсортировать массив в котором все элементы уже расположены по возрастанию, то нам нужна будет только одна итерация внешнего цикла. Поэтому в лучшем случае мы получим сложность O(n).
const testData = [ 0, 1, 2, 3, 4, 5, 6 ];
console.log(testData, `Initial testData state`);
const iterationsTestData = optimizedBubbleSort(testData);
console.log(testData, `Total iterations: ${iterationsTestData}`);
Вывод на экран:
[ 0, 1, 2, 3, 4, 5, 6 ] Initial testData state
[ 0, 1, 2, 3, 4, 5, 6 ] Total iterations: 1
Шейкерная сортировка
Coctail sort или Шейкерная сортировка - это еще одно улучшение “пузырька”. Альтернативные названия этой сортировки - сортировка перемешиванием или bidirectional sort.
Начинаем мы точно так же, как и в пузырьковой сортировке, и “выдавливаем наверх” максимальный элемент. После этого, разворачиваемся и “толкаем вниз” минимальный из оставшийся элементов.
Оказавшись в начале массива, на своих местах будет уже 2 элемента - первый и последний. Остановимся когда дойдем до середины массива. Таким образом сделаем в 2 раза меньше итераций внешнего цикла. За счет этого скорость шейкерной сортировки будет немного выше, чем у обычного пузырька.
Начнем с небольшого рефакторинга и вынесем функцию обмена наружу. Назовем ее swap :
function swap(arr, i, j) {
let tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
Реализуем алгоритм шейкерной сортировки на JavaScript:
function cocktailSort(arr) {
let left = 0;
let right = arr.length - 1;
let hasSwapped = false;
let outerLoopIterationCount = 0;
while (left < right) {
outerLoopIterationCount++;
for (let i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
hasSwapped = true;
}
}
right--;
for (let i = right; i > left; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr, i, i - 1);
hasSwapped = true;
}
}
left++;
if (!hasSwapped) {
return outerLoopIterationCount;
} else {
hasSwapped = false;
}
}
return outerLoopIterationCount;
}
И убедимся на том же тестовом массиве, что алгоритм работает и действительно делает в 2 раза меньше итераций внешнего цикла:
const testData = [ 0, -1, 4, 5, 2, -3 ];
console.log(testData, `Initial testData state`);
const iterationsTestData = cocktailSort(testData);
console.log(testData, `Total iterations: ${iterationsTestData}`);
Как видим, массив отсортирован, и количество итераций 3 вместо 6 у optimizedBubbleSort:
[ 0, -1, 4, 5, 2, -3 ] Initial testData state
[ -3, -1, 0, 2, 4, 5 ] Total iterations: 3