Алгоритм пузырьковой сортировки никак не следит за текущим состоянием массива.

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

Начни Учить Full-Stack JavaScript СЕЙЧАС!

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

Быстродействие пузырьковой сортировки в 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