Какая временная сложность у быстрой сортировки в худшем случае?

Временная сложность быстрой сортировки в худшем случае

В худшем случае временная сложность алгоритма быстрой сортировки (QuickSort) составляет O(n²), где n — количество элементов в сортируемом массиве.

Почему возникает худший случай?

Худший сценарий происходит, когда опорный элемент (pivot) на каждом шаге разделения (partitioning) выбирается неудачно — как минимальный или максимальный элемент текущего подмассива. Это приводит к максимально несбалансированному разбиению:

• Одна часть содержит все элементы, кроме опорного (n-1 элементов)
• Вторая часть — пустая или содержит только опорный элемент

Пример наихудшего сценария:

// Пример массива, отсортированного по возрастанию, при выборе первого элемента в качестве опорного
const worstCaseArray = [1, 2, 3, 4, 5, 6, 7, 8];

// Первое разбиение: pivot = 1
// Левая часть: [] (пустая)
// Правая часть: [2, 3, 4, 5, 6, 7, 8] (n-1 элементов)

Детальный анализ сложности O(n²)

В худшем случае глубина рекурсии достигает n уровней, и на каждом уровне выполняется работа O(k), где k уменьшается с n до 1:

Уровень 1: обработка n элементов
Уровень 2: обработка n-1 элементов
Уровень 3: обработка n-2 элементов
...
Уровень n: обработка 1 элемента

Общая работа: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

Когда возникает худший случай?

Худшая производительность наблюдается при:

1. Уже отсортированном массиве (по возрастанию или убыванию) при выборе первого или последнего элемента в качестве опорного
2. Постоянно минимальном или максимальном выборе опорного элемента из-за неудачной стратегии выбора
3. Массиве с одинаковыми элементами при некоторых реализациях алгоритма

Реализация, демонстрирующая худший случай:

// Наивная реализация QuickSort, подверженная худшему случаю
function quickSortWorstCase(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  
  // ВЫБОР ПЕРВОГО ЭЛЕМЕНТА В КАЧЕСТВЕ ОПОРНОГО — ПРИЧИНА ПРОБЛЕМЫ!
  const pivot = arr[left];
  let i = left + 1;
  
  // Процесс разделения
  for (let j = left + 1; j <= right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  
  // Перемещение опорного элемента на правильную позицию
  [arr[left], arr[i - 1]] = [arr[i - 1], arr[left]];
  
  // Рекурсивные вызовы для несбалансированных частей
  quickSortWorstCase(arr, left, i - 2);
  quickSortWorstCase(arr, i, right);
  
  return arr;
}

// Тестирование с худшим случаем — отсортированным массивом
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(quickSortWorstCase([...sortedArray]));

Стратегии предотвращения худшего случая

Чтобы избежать сложности O(n²), применяют следующие оптимизации:

1. Случайный выбор опорного элемента

function chooseRandomPivot(arr, left, right) {
  const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  [arr[left], arr[randomIndex]] = [arr[randomIndex], arr[left]];
  return arr[left];
}

2. Медиана трёх элементов

Выбор опорного элемента как медианы первого, среднего и последнего элементов:

function medianOfThree(arr, left, right) {
  const mid = Math.floor((left + right) / 2);
  
  // Находим медиану среди arr[left], arr[mid], arr[right]
  if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
  if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
  if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
  
  // Помещаем медиану (arr[mid]) в позицию left
  [arr[left], arr[mid]] = [arr[mid], arr[left]];
  return arr[left];
}

3. Гибридные алгоритмы

Комбинация быстрой сортировки с другими алгоритмами:

• Introsort — переключается на пирамидальную сортировку при глубокой рекурсии
• Использование сортировки вставками для небольших подмассивов (обычно менее 10 элементов)

Практическая значимость

Несмотря на худший случай O(n²), быстрая сортировка широко используется благодаря:

1. Средней временной сложности O(n log n), которая достигается в большинстве случаев
2. Отличной производительности на реальных данных, особенно при случайном выборе опорного элемента
3. Работе "на месте" с использованием O(log n) дополнительной памяти (в среднем случае)
4. Кэш-эффективности благодаря последовательному доступу к памяти

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

• Худший случай O(n²) — быстрая сортировка
• Гарантированный O(n log n) — сортировка слиянием, пирамидальная сортировка
• Быстрая сортировка обычно на практике быстрее благодаря меньшим константным множителям и лучшей локальности ссылок

В современных реализациях (например, в стандартных библиотеках C++, Java, Python) используются оптимизированные версии быстрой сортировки, которые практически исключают вероятность наступления худшего случая, сохраняя при этом все преимущества алгоритма.