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

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

Зачем нужно

Quick sort — один из самых быстрых алгоритмов сортировки на практике. Средняя сложность O(n log n), in-place (не требует дополнительной памяти O(n)), отличная производительность кэша. Часто используется в реализациях Array.sort().

Где используется

  • Стандартная библиотека многих языков
  • Сортировка больших массивов данных
  • Базы данных (ORDER BY)
  • Основа для IntroSort (гибридный алгоритм)

Предпосылки

Алгоритм

1. Выбрать опорный элемент (pivot)
2. Разделить массив на 3 части:
   - Элементы < pivot
   - Элементы === pivot
   - Элементы > pivot
3. Рекурсивно отсортировать левую и правую части
4. Объединить: [отсортированные < pivot] + [pivot] + [отсортированные > pivot]

Визуализация

Массив: [3, 6, 8, 10, 1, 2, 1]
Pivot: 3

Partition:
  left  = [1, 2, 1]    (< 3)
  pivot = [3]
  right = [6, 8, 10]   (> 3)

Рекурсия left [1, 2, 1], pivot=1:
  left  = 
  pivot = [1, 1]
  right = [2]
  → [1, 1, 2]

Рекурсия right [6, 8, 10], pivot=8:
  left  = [6]
  pivot = [8]
  right = [10]
  → [6, 8, 10]

Результат: [1, 1, 2] + [3] + [6, 8, 10] = [1, 1, 2, 3, 6, 8, 10]

Реализация в JavaScript

Простая версия (не in-place, но понятная)

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

  const pivot = array[Math.floor(array.length / 2)];
  const left = array.filter(x => x < pivot);
  const middle = array.filter(x => x === pivot);
  const right = array.filter(x => x > pivot);

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

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));
// [1, 1, 2, 3, 6, 8, 10]

In-place версия (Lomuto partition)

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSortInPlace(arr, low, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high]; // последний элемент как pivot
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

const data = [10, 7, 8, 9, 1, 5];
console.log(quickSortInPlace([...data]));
// [1, 5, 7, 8, 9, 10]

Hoare partition (более эффективная)

function quickSortHoare(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const p = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, p);
    quickSortHoare(arr, p + 1, high);
  }
  return arr;
}

function hoarePartition(arr, low, high) {
  const pivot = arr[Math.floor((low + high) / 2)];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

Выбор pivot

Выбор pivot критически влияет на производительность:

Стратегия Описание Проблема
Первый элемент arr[0] O(n^2) на отсортированных данных
Последний элемент arr[n-1] O(n^2) на отсортированных данных
Средний элемент arr[n/2] Хороший выбор для большинства случаев
Случайный arr[random] Статистически O(n log n)
Медиана трёх median(first, mid, last) Надёжный выбор 
// Медиана трёх — надёжный выбор pivot
function medianOfThree(arr, low, high) {
  const mid = Math.floor((low + high) / 2);
  // Сортируем три элемента
  if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  return mid; // средний из трёх = pivot
}

Сложность

Случай Время Память Когда
Лучший O(n log n) O(log n) Pivot всегда делит пополам
Средний O(n log n) O(log n) Случайные данные
Худший O(n^2) O(n) Pivot всегда min/max (уже отсортировано)

Стабильная: нет (простая версия с filter — да, in-place — нет).

In-place: да (Lomuto/Hoare версии).

Почему O(n^2) в худшем случае

Отсортированный массив [1, 2, 3, 4, 5], pivot = последний:

Шаг 1: pivot=5, left=[1,2,3,4], right=     → n-1 сравнений
Шаг 2: pivot=4, left=[1,2,3], right=       → n-2 сравнений
Шаг 3: pivot=3, left=[1,2], right=         → n-3 сравнений
...
Итого: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Решение: рандомизированный pivot или median-of-three.

Сравнение с другими сортировками

Параметр Quick sort Merge sort Bubble sort
Средний O(n log n) O(n log n) O(n^2)
Худший O(n^2) O(n log n) O(n^2)
Память O(log n) O(n) O(1)
Стабильная Нет Да Да
На практике Быстрейший Гарантированный Самый медленный

Частые ошибки

  1. Выбирать первый/последний элемент как pivot для отсортированных данных. Используйте рандомизацию или median-of-three
  2. Забывать базовый случай рекурсии. if (array.length <= 1) — обязательно
  3. Не учитывать нестабильность. Если порядок равных элементов важен — используйте Merge sort
  4. Простая версия с filter — O(n) памяти. Для больших данных используйте in-place версию

Практика

  1. Реализуйте простую версию quick sort с filter
  2. Реализуйте in-place версию с Lomuto partition
  3. Сравните производительность: quick sort vs Array.sort() на 100 000 элементов
  4. Проверьте: что происходит на уже отсортированном массиве?

Связанные темы

Ресурсы

  • visualgo.net/en/sorting — визуализация
  • Grokking Algorithms, глава 4 (Aditya Bhargava)
  • Introduction to Algorithms (CLRS), глава 7