Почему quicksort с плохим пивотом ломается именно на отсортированном массиве

Вопрос проверяет не знание алгоритма, а понимание того, что «средняя сложность O(n log n)» — это утверждение про случайный вход, а не гарантия.

Если пивот всегда берётся как первый элемент массива, партишн на отсортированном по возрастанию входе каждый раз даёт разбиение 1 и n-1. Один элемент уходит в одну часть, все остальные — в другую. Рекурсия получает глубину n вместо log n, и суммарная работа партишна на каждом уровне даёт O(n²).

Это не редкий частный случай. Отсортированные или почти отсортированные входы — обычная ситуация в проде: повторная сортировка уже упорядоченных данных, вставка в конец лога, обработка временных рядов.

private static int partition( int[] array, int lo, int hi) { int pivot = array[lo]; int i = lo + 1; for (int j = lo + 1; j <= hi; j) { if (array[j] < pivot) { swap(array, i, j); i; } } swap(array, lo, i - 1); return i - 1; }

Тут пивот жёстко зафиксирован на array[lo]. На отсортированном массиве каждый вызов partition отделяет ровно один элемент.

Дальше спросят, как исправить: медиана трёх (первый, средний, последний элемент) снижает вероятность плохого разбиения на бытовых входах, но не защищает от специально построенного массива. Случайный пивот меняет модель атаки полностью — противник не может предсказать, какой элемент будет выбран, поэтому расчёт худшего случая теряет смысл. Полная защита — introsort: если глубина рекурсии превышает log n от размера, переключаемся на heapsort, у которого худший случай гарантированно O(n log n).

Средняя сложность — характеристика алгоритма на случайном входе. Худший случай — характеристика на конкретном входе, который вы не контролируете.

Тренажёр: 600 вопросов, мок с таймером, план повторов

senior·base — что спрашивают на самом деле

В этом посте были ссылки, но мы их удалили по правилам Сетки