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

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

🧠 Разделяй и властвуй

Divide and Conquer (разделяй и властвуй) — это мощная стратегия решения задач. Идея: если задача слишком большая, раздели её на меньшие подзадачи, реши каждую, объедини результаты.

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

Почему это работает? После каждого разделения pivot стоит на своём правильном месте — элементы слева меньше него, справа больше. Если рекурсивно упорядочить обе половины, весь массив окажется отсортированным.

🎯 Как выбирают опорный элемент (pivot)

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

В нашей учебной реализации будем использовать последний элемент как pivot — это самый простой вариант для понимания алгоритма. Для боевого кода лучше рандомизация.

📊 Пошаговая визуализация: [5, 3, 8, 1, 4]

Разберём как quickSort работает с массивом [5, 3, 8, 1, 4]. Для наглядности используем фильтрацию через filter — чуть медленнее «in-place» варианта, но идеально читаемо.

Посмотрите на структуру: каждый раз массив делится на две части относительно pivot. Pivot занимает своё финальное место, затем рекурсия обрабатывает левую и правую части независимо. Дерево вызовов растёт в глубину log n — отсюда O(n log n).

💻 Наглядная реализация через filter

Начнём с самой читаемой версии — через filter. Она не самая эффективная по памяти, зато идеально иллюстрирует алгоритм.

function quickSort(arr) {
  // Базовый случай: массив из 0 или 1 элемента уже отсортирован
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1]; // берём последний элемент как pivot

  // Все элементы МЕНЬШЕ pivot
  const left = arr.slice(0, -1).filter(x => x <= pivot);

  // Все элементы БОЛЬШЕ pivot
  const right = arr.slice(0, -1).filter(x => x > pivot);

  // Рекурсивно сортируем обе части, потом соединяем
  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([5, 3, 8, 1, 4]));
// [1, 3, 4, 5, 8]

console.log(quickSort([10, 2, 7, 5, 1, 9, 3]));
// [1, 2, 3, 5, 7, 9, 10]

Разберём код построчно:

• if (arr.length <= 1) return arr — базовый случай рекурсии: один элемент или пустой массив уже «отсортированы»
• pivot = arr[arr.length - 1] — берём последний элемент как опорный
• filter(x => x <= pivot) — все меньшие или равные уходят влево
• filter(x => x > pivot) — все большие уходят вправо
• [...quickSort(left), pivot, ...quickSort(right)] — рекурсия + сборка результата

🔢 Почему O(n log n)

Давайте поймём, откуда берётся n log n интуитивно.

При хорошем выборе pivot каждый вызов делит массив примерно пополам. Это означает:

• log n уровней рекурсии — каждый раз массив делится пополам, и так пока не дойдём до единичных элементов
• На каждом уровне — n работы — суммарно на каждом уровне рекурсии обрабатываем все n элементов
• Итого: n × log n

Уровень 0: [8 элементов]                    — 8 операций
Уровень 1: [4 элемента] [4 элемента]         — 4 + 4 = 8 операций
Уровень 2: [2][2]       [2][2]               — 2+2+2+2 = 8 операций
Уровень 3: [1][1][1][1] [1][1][1][1]         — 8 × 1 = 8 операций
                                               Итого: 4 уровня × 8 = log₂(8) × 8

⚖️ QuickSort vs пузырьковая: сравнение

Наглядно видно, почему QuickSort вытеснил пузырьковую сортировку в реальном коде:

При миллионе элементов QuickSort быстрее пузырьковой сортировки в 50 000 раз. Это и есть сила алгоритмов.

✅ Итоги урока

• QuickSort использует стратегию «разделяй и властвуй»
• Три шага: выбрать pivot, разделить на меньшее/большее, рекурсивно отсортировать части
• Наглядная реализация через filter — хорошо для понимания, чуть медленнее по памяти
• Сложность O(n log n) в среднем, O(n²) в худшем (неудачный pivot)
• Рандомизация pivot защищает от вырождения в O(n²)
• При миллионе элементов — в 50 000 раз быстрее пузырьковой сортировки
• В реальном коде — используйте встроенный .sort(), но QuickSort важен для понимания divide & conquer