От пузырька до Quick Sort: разбираемся в алгоритмах сортировки на JavaScript

Автор:  Анастасия Мальцева, фронтенд-разработчик. 

Работала со Сбером, ВТБ, Газпромом. Спикер на Holy.js, FrontendConf, OpenConf
и на  митапах Moscow JS, Piter JS, Erevan JS, Moscow CSS.
Проводила вебинары в Хекслете. Ведёт канал «Код и кофе» в Телеграм.

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

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

В этой статье разберём три классических алгоритма сортировки:

• Bubble Sort — последовательно сравнивает соседние элементы и меняет их местами.

• Merge Sort — разбивает массив на части, сортирует их и объединяет обратно.

• Quick Sort — выбирает опорный элемент и перераспределяет остальные относительно него.

Реализуем эти алгоритмы на JavaScript, разберём их работу и сравним их сложность на массивах разного размера.

Заодно выясним, есть ли оптимальный алгоритм и стоит ли вообще писать собственную сортировку, когда есть Array.prototype.sort().

Зачем разбираться в алгоритмах сортировки?

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

Самый очевидный подход — сравнивать элементы между собой и менять местами, если они стоят в неправильном порядке. Это «метод пузырька», он даёт верный результат, но на больших массивах количество сравнений может оказаться огромным.

Другой подход — «сортировка слиянием»: разбить массив на части, отсортировать каждую часть, а затем собрать части обратно в единый массив. А можно выбрать один элемент и распределить остальные относительно него — это «алгоритм быстрой сортировки».

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

Что такое алгоритмическая сложность

Для оценки эффективности алгоритмов используют нотацию Big O. Она описывает, как растут затраты времени или памяти при увеличении объёма входных данных n.

Для наших алгоритмов важны две оценки:

• O(n²) — количество операций растёт квадратично. Если увеличить массив n  в 10 раз, время выполнения может вырасти примерно в n² — в 100 раз.

• O(n log n) — количество операций (а значит, и время выполнения) растёт значительно медленнее. Увеличение массива n в 10 раз приводит к росту времени выполнения примерно в 12–13 раз для массивов от тысячи до миллиона элементов.

При этом Big O не учитывает стоимость отдельных операций, особенности реализации и оптимизации JavaScript-движка.

Время — не единственный критерий

При выборе алгоритма важны и другие характеристики:

• Дополнительная память. Одни алгоритмы сортируют массив на месте, другим нужны вспомогательные массивы — а для этого нужна дополнительная память.

• Стабильность. Стабильная сортировка сохраняет исходный порядок элементов с одинаковыми значениями ключа. Например, если отсортировать сотрудников по возрасту, сотрудники одного возраста останутся в прежнем порядке. Нестабильные сортировки такой порядок не гарантируют: порядок элементов с одинаковым ключом может поменяться (например, изменится порядок сотрудников одного возраста).

• Поведение на разных данных. Скорость алгоритма зависит от порядка элементов. Алгоритм может отлично работать на случайных массивах, но существенно замедляться на определённых входных последовательностях.

Теперь посмотрим, как эти различия проявляются на практике. Начнём с самого простого алгоритма — сортировки пузырьком.

Сортировка пузырьком (Bubble Sort)

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

Например, массив [5, 3, 8, 1, 2] после первого прохода станет [3, 5, 1, 2, 8]: число 8 уже на своём месте.

function bubbleSort(arr) {
  const result = [...arr];
  for (let i = 0; i < result.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < result.length - 1 - i; j++) {
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return result;
}
bubbleSort([5, 3, 8, 1, 2]);
// [1, 2, 3, 5, 8]

Мы копируем исходный массив, чтобы не изменять его, а флаг swapped позволяет завершить сортировку раньше, если массив уже упорядочен. После каждого прохода проверять последние i элементов больше не нужно: они уже отсортированы.

Сложность:

• Сложность по времени:

  • В среднем и худшем случае — O(n²).

  • В лучшем случае — O(n), если массив уже отсортирован.

• Сложность по памяти — O(n): алгоритм копирует массив и для этого ему нужна дополнительная память.

Если сортировать исходный массив на месте — сложность по памяти будет равна O(1), то есть вообще не будет зависеть от длины массива.

Bubble Sort прост в реализации, но квадратичная сложность делает его непрактичным для больших массивов. Посмотрим на алгоритм, который справляется с сортировкой значительно эффективнее.

Сортировка слиянием (Merge Sort)

Merge Sort использует принцип «разделяй и властвуй»: разбивает массив на две половины, рекурсивно сортирует каждую, а затем объединяет их в один отсортированный массив.

Например, [5, 3, 8, 1, 2] сначала разделится на [5, 3] и [8, 1, 2]. Массив рекурсивно делится, пока части не станут длиной не больше одного элемента; слияние каждой пары начинается после обработки её половин.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

mergeSort([5, 3, 8, 1, 2]);
// [1, 2, 3, 5, 8]

Функция merge() сравнивает первые ещё не обработанные элементы двух отсортированных массивов и добавляет меньший в результат. Когда один массив заканчивается, оставшиеся элементы второго добавляются без дополнительных сравнений.

Сложность:

• По времени — O(n log n) в лучшем, среднем и худшем случаях.

• По памяти — O(n): дополнительная память нужна для хранения промежуточных массивов.

В отличие от Bubble Sort, Merge Sort сохраняет предсказуемую производительность даже на больших массивах. За это приходится платить дополнительным расходом памяти.

Быстрая сортировка (Quick Sort)

Quick Sort тоже использует принцип «разделяй и властвуй», но вместо слияния отсортированных половин выбирает опорный элемент (pivot) и распределяет остальные элементы относительно него: меньшие — слева, большие — справа. Затем алгоритм рекурсивно сортирует обе части.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const equal = [];
  const right = [];

  for (const value of arr) {
    if (value < pivot) {
      left.push(value);
    } else if (value > pivot) {
      right.push(value);
    } else {
      equal.push(value);
    }
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

quickSort([5, 3, 8, 1, 2]);
// [1, 2, 3, 5, 8]

В этой реализации элементы, равные pivot, собираются отдельно. Это упрощает обработку повторяющихся значений. Для простоты мы создаём новые массивы, хотя существуют и реализации, которые сортируют исходный массив на месте.

Сложность:

• По времени:

  • Классическая оценка лучшего случая Quick Sort — O(n log n), но трёхчастное разбиение в нашей формуле позволяет добиться O(n), когда все элементы равны.

  • В среднем — O(n log n).

  • В худшем случае — O(n²), если разбиения получаются сильно неравномерными.

• По памяти — зависит от реализации

  • В нашей реализации — в среднем O(n): здесь создаются новые массивы на каждом уровне рекурсии.

  • В других реализациях можно уменьшить расход памяти до O(log n)

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

Сравнение алгоритмов

* В той реализации Bubble Sort, которую мы показали в коде, массив копируется, поэтому сложность по памяти — O(n). O(1) достигается при сортировке на месте.

Для Quick Sort в таблице указаны стандартные оценки. В приведённой реализации используются новые массивы, поэтому дополнительные затраты памяти выше, чем у классической реализации на месте.

Какой алгоритм выбрать?

• Bubble Sort — для изучения основ алгоритмов, но не для практической сортировки больших массивов.

• Merge Sort — когда важна гарантированная сложность O(n log n) и допустимы дополнительные затраты памяти.

• Quick Sort — когда нужна эффективная сортировка и можно подобрать подходящую реализацию с хорошим выбором pivot.

В обычном JavaScript-коде чаще всего достаточно встроенного Array.prototype.sort(). Посмотрим, как им пользоваться и почему сортировка чисел требует отдельного компаратора.

А что насчёт sort() в JavaScript?

В большинстве случаев собственная реализация сортировки не нужна: в JavaScript есть готовый метод Array.prototype.sort(). Но по умолчанию он сравнивает элементы как строки, поэтому [10, 2, 5].sort() вернёт [10, 2, 5], а не [2, 5, 10].

Для чисел передаём компаратор:

[10, 2, 5].sort((a, b) => a - b);
// [2, 5, 10]

Объекты можно сортировать по нужному полю:

const users = [
  { name: 'Anna', age: 30 },
  { name: 'Ivan', age: 22 },
  { name: 'Maria', age: 27 },
];

users.sort((a, b) => a.age - b.age);

Метод sort() изменяет исходный массив. Если же исходный массив нужно сохранить — используйте toSorted() или предварительно скопируйте массив.

Встроенная сортировка не обязана использовать какой-то один из разобранных алгоритмов: конкретная реализация зависит от JavaScript-движка.

Например, V8 использует TimSort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием. Сортировка вставками (Insertion Sort) — алгоритм, который последовательно берёт очередной элемент и вставляет его на правильное место в уже отсортированной части массива. 

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