Какая сложность у сортировок quicksort и пузырьковой

Что проверяют

Знаете ли вы не только оценки, но и при каких входах наступает худший случай и как его избегают. Для Java следом спрашивают, что использует Arrays.sort и почему для объектов алгоритм другой.

Как отвечать

• quicksort, время: в среднем и в лучшем случае O(n log n), в худшем O(n²). Худший случай наступает, когда опорный элемент раз за разом оказывается минимумом или максимумом: наивный выбор первого элемента на отсортированном массиве или много одинаковых значений при разбиении на две части;
• quicksort, память: O(log n) на стек, если рекурсия идёт сначала в меньшую часть. Наивная реализация в худшем случае уходит на глубину n и может кончиться StackOverflowError;
• quicksort, свойства: сортирует на месте, но не стабилен, равные элементы могут поменяться местами;
• пузырьковая, время: O(n²) в среднем и худшем. O(n) на отсортированном массиве получается только с флагом «за проход не было обменов», без него всегда O(n²);
• пузырьковая, свойства: O(1) дополнительной памяти, стабильна, но делает много обменов и проигрывает даже сортировке вставками.

Защита quicksort от худшего случая: случайный опорный элемент, медиана из трёх, трёхпутевое разбиение для дубликатов, introsort с переходом на heapsort при слишком глубокой рекурсии.

Что в JDK. Arrays.sort для примитивов использует Dual-Pivot Quicksort с двумя опорными элементами, а в современных версиях при глубокой рекурсии переключается на heapsort. Для объектов Arrays.sort(Object[]), Collections.sort и List.sort используют TimSort: он стабилен, гарантирует O(n log n) и почти линеен на частично упорядоченных данных. Стабильность для объектов важна, потому что их часто сортируют по нескольким полям последовательно.

Где спотыкаются

Говорят, что худший случай quicksort это «отсортированный массив» без уточнения. Это верно только для наивного выбора опорного элемента.

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

Считают, что Arrays.sort для объектов тоже quicksort. Тогда не получается объяснить, почему после сортировки по фамилии, а затем по отделу, внутри отдела фамилии остаются по алфавиту.