Быстрая сортировка: метод «разделяй и властвуй»

Быстрая сортировка (quicksort) — алгоритм, основанный на принципе «разделяй и властвуй»: большая задача делится на малые, они решаются отдельно, а результаты объединяются. На первом шаге из массива выбирается опорный элемент. Остальные элементы разделяются на три группы: меньшие опорного, равные ему и большие.

Затем группы меньших и больших элементов сортируются тем же способом, то есть рекурсивно. Если часть состоит из одного элемента или пуста, она уже упорядочена — это условие остановки рекурсии. Краткая запись на Python: def qs(a): return a if len(a) <= 1 else qs([x for x in a if x < a[0]]) + [x for x in a if x == a[0]] + qs([x for x in a if x > a[0]]).

Пусть массив — 5 2 8 1 5, опорный элемент — 5. Меньшие: 2 1, равные: 5 5, большие: 8. Сортировка 2 1 даёт 1 2, итог — 1 2 5 5 8. Если опорный элемент делит массив примерно пополам, глубина рекурсии около log₂ n, а общий объём работы пропорционален n · log₂ n; для 1 000 000 элементов это порядка 20 миллионов операций вместо 500 миллиардов у сортировки пузырьком.

Худший случай быстрой сортировки — когда опорным каждый раз оказывается наименьший или наибольший элемент: тогда время приближается к n². Чтобы этого избежать, опорный элемент берут из середины или случайно. На практике для сортировки применяют готовую функцию Python sorted(), а быстрая сортировка — лучший пример для изучения идеи «разделяй и властвуй».

Главное

• Быстрая сортировка делит массив вокруг опорного элемента на меньшие, равные и большие.
• Меньшие и большие части сортируются тем же способом рекурсивно.
• В среднем время пропорционально n · log₂ n — намного быстрее сортировки пузырьком.
• В худшем случае (опорный каждый раз крайний элемент) время приближается к n².
• На практике используют готовую функцию sorted().