Что это?
Quicksort — это алгоритм «разделяй и властвуй» для сортировки списков данных. Он работает, упорядочив один элемент (стержень) относительно двух других групп элементов (те, которые меньше и больше, чем свод), а затем быстро сортируя эти две группы. Этот процесс повторяется для все меньших и меньших частей списка, пока весь список не будет отсортирован.
Как это работает?
Быстрая сортировка построена вокруг следующей идеи:
Массив сортируется, если для любого заданного элемента e:
- Элементы слева от e меньше (или равны) e
- Элементы справа от e больше (или равны) e
- Элементы слева от e отсортированы
- Элементы справа от e отсортированы
При быстрой сортировке мы часто называем произвольно выбранный элемент опорным элементом, а две группы меньших и больших элементов — разделами.
Быстрая сортировка работает по существу:
1. Выбор произвольного элемента e
2. Разделение массива таким образом, чтобы:
● Все элементы слева от e меньше (или равно) e
● Все элементы справа от e больше (или равно) e
3. Быстрая сортировка левого и правого разделов
Выполнение
Примечания
- Быстрая сортировка выполняется за время O(N log N) (средний случай)
- Быстрая сортировка выполняется за O(N²) (в худшем случае)
- Существует множество способов выбора раздела. Время наихудшего случая достигается, когда выбранный опорный элемент всегда является минимумом/максимумом.
- Для быстрой сортировки требуется O(1) пробела. Единственное требование к памяти — достаточно места для замены двух элементов (и нескольких итераторов).
