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

Краткое описание

Алгоритм «разделяй и властвуй»: выбирает опорный элемент (pivot), разбивает массив на элементы меньше/больше pivot и рекурсивно сортирует части. В среднем Quick Sort работает за O(n log n), но при неудачном выборе pivot может деградировать до O(n²).

Когда использовать

• Большие массивы в памяти — на практике Quick Sort часто очень быстрый из‑за небольших накладных расходов и хорошего поведения на кэше
• Ограниченная доп. память — типичная реализация сортирует «на месте» (in-place), доп. память в среднем O(log n) на стек рекурсии
• Нужна скорость, но не нужна стабильность — Quick Sort обычно нестабилен (может менять порядок равных элементов)
• Можно контролировать pivot — рандомизация pivot заметно снижает шанс попасть в худший случай на «плохих» входах

Когда не стоит использовать:

• Нужна гарантированная O(n log n) в худшем случае — Quick Sort может дать O(n²) при неудачном выборе pivot
• Требуется стабильность — порядок равных элементов может измениться
• Ограниченный стек — рекурсия может быть глубокой в худшем случае (O(n))

---

С объяснением логики работы

/**
 * Quick Sort (in-place) с рандомизированным pivot.
 * Сортирует массив чисел по возрастанию.
 *
 * Идея:
 * 1) Выбираем pivot (опорный элемент)
 * 2) Делим массив так, чтобы:
 *    - слева были элементы <= pivot
 *    - справа были элементы  > pivot
 * 3) Рекурсивно сортируем левую и правую часть
 */
 
// Вспомогательная функция: обмен элементов массива местами
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
 
/**
 * Разбиение Lomuto partition:
 * - pivot берём как arr[right]
 * - i указывает, куда ставить следующий элемент <= pivot
 * Возвращает итоговый индекс pivot после разбиения.
 */
function partitionLomuto(arr, left, right) {
  const pivot = arr[right];       // опорный элемент
  let i = left;                   // граница области "<= pivot"
 
  // j пробегает по всем элементам, кроме pivot (right)
  for (let j = left; j < right; j++) {
    // Если текущий элемент должен быть слева (<= pivot)
    if (arr[j] <= pivot) {
      // Меняем местами arr[j] и arr[i], тем самым расширяя левую часть
      swap(arr, i, j);
      i++;
    }
  }
 
  // После цикла i — место, куда должен встать pivot
  swap(arr, i, right);
  return i;
}
 
/**
 * Основная функция Quick Sort.
 * Сортирует arr "на месте" и возвращает arr (для удобства).
 */
function quickSort(arr, left = 0, right = arr.length - 1) {
  // Базовый случай: 0 или 1 элемент — уже отсортировано
  if (left >= right) return arr;
 
  // Рандомизируем pivot: выбираем случайный индекс и ставим его в конец (right),
  // чтобы partitionLomuto всегда использовал arr[right] как pivot.
  const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
  swap(arr, pivotIndex, right);
 
  // Разбиваем массив, получаем позицию pivot в окончательном месте
  const p = partitionLomuto(arr, left, right);
 
  // Теперь:
  // arr[left .. p-1] <= arr[p]
  // arr[p+1 .. right] > arr[p]
  // Рекурсивно сортируем обе части
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
 
  return arr;
}
 
// Пример
const a = [10, 7, 8, 9, 1, 5];
quickSort(a);
console.log(a); // [1, 5, 7, 8, 9, 10]

---

С анализом сложностей

/**
 * Quick Sort (in-place, randomized pivot)
 *
 * ВРЕМЕННАЯ СЛОЖНОСТЬ:
 * - Лучший случай:   O(n log n) — разбиения близки к половинам (pivot каждый раз “удачный”)
 * - Средний случай:  O(n log n) — ожидаемая сложность при случайном/рандомизированном pivot
 * - Худший случай:   O(n²)      — разбиения крайне неравномерные (например, 0 и n-1)
 *
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
 * - Доп. память:     O(1)       — разбиение делаем без дополнительных массивов (in-place)
 * - Стек рекурсии:   O(log n) в среднем, O(n) в худшем случае (глубокая рекурсия)
 *
 * ВАЖНО:
 * - Обычно НЕ стабильный алгоритм: равные элементы могут поменяться местами.
 * - Рандомизация pivot снижает вероятность худшего случая на "плохих" входах.
 */
 
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
 
function partitionLomuto(arr, left, right) {
  // Время: O(right-left) сравнений, т.е. O(n) на текущем уровне
  // Память: O(1)
  const pivot = arr[right];
  let i = left;
 
  for (let j = left; j < right; j++) {
    // Каждая проверка O(1), всего ~n проверок на уровне
    if (arr[j] <= pivot) {
      // Swap O(1)
      swap(arr, i, j);
      i++;
    }
  }
 
  swap(arr, i, right);
  return i;
}
 
function quickSort(arr, left = 0, right = arr.length - 1) {
  // База рекурсии — O(1)
  if (left >= right) return arr;
 
  // Рандомизированный pivot: O(1)
  const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
  swap(arr, pivotIndex, right);
 
  // Разбиение: O(n) на текущем диапазоне
  const p = partitionLomuto(arr, left, right);
 
  // Рекурсия:
  // T(n) = T(k) + T(n-k-1) + O(n), где O(n) — partition
  // - При хороших разбиениях: глубина ~log n, суммарно O(n log n)
  // - При плохих разбиениях: глубина ~n, суммарно O(n²)
  quickSort(arr, left, p - 1);
  quickSort(arr, p + 1, right);
 
  return arr;
}