Как работает быстрая сортировка (quicksort)

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

Умеете ли вы объяснить разбиение, а не только пересказать «разделяй и властвуй», и знаете ли, откуда берётся худший случай. Следом часто просят написать partition на Swift прямо на собеседовании или спрашивают, что использует стандартный sort().

Как отвечать

Алгоритм в три шага: выбрать опорный элемент (pivot), переставить массив так, чтобы слева оказались элементы меньше опорного, а справа больше, и рекурсивно отсортировать обе части. Вся суть в разбиении:

• схема Ломуто: один указатель проходит массив и перекидывает меньшие элементы в начало, опорный берётся последним. Пишется проще, но обменов больше и на повторах она деградирует;
• схема Хоара: два указателя идут навстречу друг другу и меняют пары, обменов меньше;
• трёхпутевое разбиение: отдельная зона для элементов, равных опорному. Спасает на массивах с большим числом одинаковых значений.

Сложность: в среднем O(n log n), в худшем O(n²), когда разбиение раз за разом получается перекошенным. Классический триггер это уже отсортированный массив при опорном элементе с края. Лечится случайным опорным или медианой из трёх. Память: in-place версия берёт только стек рекурсии, O(log n), если рекурсия идёт в меньшую часть, а большая обрабатывается циклом. Сортировка нестабильна.

Для iOS-разработчика полезно добавить контекст. В Swift пишут in-place вариант на inout [T] с swapAt(_:_:) и ограничением T: Comparable. Версия с filter и склейкой массивов короче, но выделяет память на каждом уровне и перестаёт быть быстрой. А стандартный sort() в Swift с пятой версии построен на варианте timsort, а не на quicksort, так что своя реализация в продовом коде не нужна.

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

Называют главным преимуществом экономию памяти и тут же пишут версию с filter, которая копирует массив на каждом шаге.

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

Ошибаются в границах индексов в partition и получают бесконечную рекурсию на двух элементах или выход за пределы массива. Проговорите инварианты указателей вслух, прежде чем писать код.