Если я скажу вам, что QuickSort — это O(n*logn), вы, вероятно, будете возражать и спорить со своей точкой зрения. Если это так, вы можете найти эту статью откровением.
Действительно, у меня было следующее обсуждение бесчисленное количество раз:
Человек А:QuickSort — такой плохой алгоритм.
Я: Почему?
Человек А: Ну, во-первых, это O(n*n) в худшем случае.
Я: Это верно только в том случае, если мы выбираем опорную точку случайным образом.
Человек А: Какие ты говоришь о? Неважно, как вы выберете опорную точку, это всегда O(n*n) наихудший случай.
Итак, да, если мы выберем опорную точку случайным образом/произвольно, QuickSort может превратиться в SelectSort, что сделает его O(n*n). Однако мы можем выбрать точку опоры, чтобы исключить этот наихудший случай, сделав быструю сортировку в худшем случае O(n*logn).
В этой статье сначала будет рассмотрена классическая быстрая сортировка, которая выбирает средний элемент в качестве опорного и демонстрирует реализацию на C++. Затем мы рассмотрим всегда O(n*logn) QuickSort.
O(n*n) Быстрая сортировка
QuickSort — это алгоритм рекурсивного разделения. Алгоритм разделения будет перемещать элементы последовательности, начиная с элементов, которые удовлетворяют предикату, за которыми следуют элементы, которые не удовлетворяют.
# Before partition 1 2 3 4 5 6 7 8 9 # After partition with is_even 2 4 6 8 1 3 5 7 9
Для быстрой сортировки нам требуется трехсторонний раздел, который разделит последовательность на элементы, меньшие, чем выбранная опорная точка, равные опорной точке и, наконец, большие, чем выбранная опорная точка.
# Before partition with pivot 5 9 9 5 5 5 3 2 1 # After partition with pivot 5 3 2 1 5 5 5 9 9
В C++ у нас есть стандартное двустороннее разделение: алгоритм std::partition. Но давайте быстро посмотрим, как вы могли бы реализовать это самостоятельно:
Это общая версия алгоритма разделения. Давайте сначала пройдемся по реализации. Алгоритм использует два итератора (семантика C++ равна [first,last)). Сначала мы находим самый левый элемент, который не удовлетворяет предикату (строка 6), и если его нет, мы уже закончили (строка 7).
Затем мы проверяем каждый из оставшихся элементов (строки 9–10), и если элемент действительно удовлетворяет предикату, мы должны переместить его перед всеми элементами, которые не удовлетворяют предикату (строки 12–13). std::iter_swap поменяет местами элементы позади итераторов.
Глядя на реализацию, мы теперь можем сформулировать концепции C++20, которые требуются для этого алгоритма. Передаваемые итераторы должны удовлетворять std::forward_iterator (для ++ и !=) и std::indirectly_swapable (для std::iter_swap). Условие должно удовлетворять концепции std::predicate (вызов, который возвращает логическое значение). У меня есть отдельная статья о концепциях C++20, если вы хотите узнать больше.
Быстрая сортировка
Создание базовой быстрой сортировки относительно просто. Тем не менее, мы должны быть осторожны с нашей точкой опоры:
Вместе вызовы двух разделов представляют собой трехсторонний раздел (строки 10 и 11). Мы помещаем нашу опорную точку в конец подпоследовательности, а затем перемещаем ее обратно в место, указанное точкой разбиения pp2, которая указывает на первый элемент, больший, чем опорная (строки 7–8 и 13–14). После разделения и фиксации опорной точки мы рекурсивно (строки 16–17) и обнаруживаем терминальное состояние с пустым диапазоном (строки 4–5).
В качестве альтернативы перемещению точки поворота мы могли бы взять копию значения. Эта версия лучше подходит для элементов, которые дешево заменить, но дорого скопировать.
Эта простая версия быстрой сортировки прекрасно работает, но поскольку мы выбираем опорный элемент в качестве среднего элемента first + std::distance(first, last)/2, он может превратиться в O(n*n), если мы всегда попадаем в минимальный или максимальный элемент. Итак, давайте поговорим о том, что нам нужно сделать, чтобы добиться всегда O(n*logn) QuickSort.
O(n*logn) Быстрая сортировка
Пока мы произвольно выбираем опорную точку, в худшем случае мы всегда будем переходить от QuickSort к SelectionSort. Нам нужен метод выбора опорной точки, который выполняется за O(n) и всегда позволяет выбрать хорошую опорную точку.
Итак, давайте обсудим метод, который в худшем случае даст нам опорную точку, которая разбивает последовательность в соотношении 3:7.
Медиана медиан
Алгоритм соответствует своему названию. Сначала мы разбиваем последовательность на фрагменты по пять элементов, вычисляем медиану для каждого фрагмента, а затем выбираем медиану из этих медиан в качестве опорной точки.
Хотя это звучит просто, реализация включает в себя QuickSelect и взаимную рекурсию и может быть довольно сложной, поэтому мы будем делать это шаг за шагом.
Соотношение 3:7
Когда мы выбираем медиану медиан, мы знаем, что медиана половины пятиэлементных фрагментов ниже, чем наша медиана медиан, а половина пятиэлементных фрагментов имеет медиана выше, чем наша медиана медиан.
Для фрагментов с более низкой медианой мы знаем, что есть два элемента ниже самой медианы, поэтому мы знаем, что каждый из этих фрагментов имеет по крайней мере три элемента ниже медианы медианы (медиана фрагмента и два других элемента). ).
Если мы посчитаем это, это (половина фрагментов) * 3 элемента = (1/2) * (n/5) * 3 = n * (3/10). Следовательно, как минимум 30% элементов будут ниже медианы медиан (и аналогичная логика работает для элементов выше).
Реализация
Во-первых, нам нужен способ выбрать медиану из фрагмента из пяти элементов.
Обратите внимание, что сложность здесь не имеет значения, так как мы всегда выбираем не более пяти элементов.
Далее наша медиана реализации медиан:
Сначала нам нужно перебрать куски из пяти элементов (строки 11–13), переместив соответствующие медианы в начало последовательности (строки 15–17), а затем вызвать quick_select, чтобы выбрать правильную медиану из этих медиан (строка 21).
Реализация QuickSelect должна выглядеть знакомо. Действительно, это в значительной степени односторонняя быстрая сортировка. После разделения мы знаем, где находится наш целевой элемент, поэтому мы ищем только этот раздел.
Обратите внимание, что мы действительно вызываем медиану медиан из QuickSelect (строка 8), которая затем вызывает QuickSelect обратно, чтобы вернуть фактическую медиану медиан.
Все это вместе обеспечивает сложность O(n) в наихудшем случае для QuickSelect и сложность O(n*logn) в наихудшем случае для QuickSort.
Практические соображения
Итак, теперь вы можете задаться вопросом, почему мы не используем этот подход повсеместно. Что ж, медиана медиан — отличный пример того, почему нотация с большой буквой «О» не раскрывает всей истории.
Да, этот подход устраняет наихудшую сложность. Однако на практике накладные расходы на дополнительные сравнения и перемещения, необходимые для реализации этого алгоритма, делают его непрактичным. Поэтому вместо этого вы найдете IntroSort (QuickSort + HeapSort) или какой-либо другой гибридный подход в реализации вашей библиотеки.
В то же время алгоритмы сортировки являются активной областью исследований, и в некоторых документах отмечается, что вариации QuickSort с интеллектуальным опорным выбором могут быть практичными.
Ссылки и технические примечания
Репозиторий со всем представленным кодом доступен по адресу: https://github.com/HappyCerberus/article-quicksort.
Чтобы узнать больше о медиане медиан, включая доказательство сложности, ознакомьтесь со статьей в Википедии.
Спасибо за чтение
Спасибо, что прочитали эту статью. Вам понравилось?
Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.
