23. Расскажите про быструю сортировку.

Выберем некоторый опорный элемент(pivot). После этого перекинем все элементы, меньшие его, налево, а большие – направо. Для этого используются дополнительные переменные - значения слева и справа, которые сравниваются с pivot.

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

Асимптотика: O(n*log(n)) в среднем и лучшем случае. Наихудшая оценка O(n^2) достигается при неудачном выборе опорного элемента.

Предыдущий вопрос: 22. Расскажите про пузырьковую сортировку.

Следующий вопрос: 24. Расскажите про сортировку слиянием.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне