Важным фактом, который вы должны знать, является то, что в массиве различных элементов быстрая сортировка со случайным выбором раздела будет выполняться в O (n lg n). Есть много хороших доказательств этого, и the one on Wikipedia действительно имеет довольно хорошее обсуждение этого. Если вы готовы пойти на несколько менее формальное доказательство, которое в основном математически звучит, интуиция идет следующим образом. Всякий раз, когда мы выбираем стержень, допустим, что «хороший» стержень является стержнем, который дает нам по крайней мере 75%/25% раскола; то есть он больше, чем по меньшей мере 25% элементов и не более 75% элементов. Мы хотим связать количество раз, когда мы можем получить стержень этого типа до того, как алгоритм завершится. Предположим, что мы получаем k расщеплений этого типа и рассмотрим размер самой большой подзадачи, сгенерированной таким образом. Он имеет размер не более (3/4) k n, так как на каждой итерации мы избавляемся от по меньшей мере четверти элементов. Если мы рассмотрим конкретный случай, когда k = log 3/4 (1/n) = log 4/3 n, тогда размер наибольшей подзадачи после k хороших опорных точек будет равен 1, а рекурсия будет равна стоп. Это означает, что если мы выберем O (lg n) хорошие повороты, рекурсия закончится. Но на каждой итерации, какой шанс получить такой стержень? Ну, если мы произвольно выбираем шарнир, тогда вероятность 50% находится в середине 50% элементов и так далее, мы выберем два случайных стержня, прежде чем мы получим хороший опорный стержень. Каждый шаг выбора точки поворота занимает время O (n), и поэтому мы должны потратить примерно O (n) раз, прежде чем получить каждый хороший стержень. Поскольку мы получаем максимум O (lg n) хороших опорных точек, общая продолжительность выполнения O (n lg n) при ожидании.
Важная деталь в приведенном выше обсуждении заключается в том, что если вы замените разнесение на 75%/25% любым постоянным расколом - скажем, (100 - k%)/k% split - асимптотический анализ по аналогии. Вы получите, что quicksort берет, в среднем, время O (n lg n).
Причина, по которой я упомянул это доказательство, заключается в том, что он дает вам хорошую основу для размышления о том, как выбрать опорный стержень в быстрой сортировке. Если вы можете выбрать точку опоры, которая находится близко к середине на каждом этапе, вы можете гарантировать время выполнения O (n lg n).Если вы не можете гарантировать, что на любой итерации вы получите хорошую точку опоры, но можете сказать, что при ожидании требуется только постоянное количество итераций, прежде чем вы получите хороший стержень, тогда вы также можете гарантировать O (n lg n) ожидаемое время выполнения.
Учитывая это, давайте посмотрим на предлагаемые вами сводные схемы. Для получения (а), если массив является случайным, выбирая первый элемент в качестве оси поворота, по существу, такой же, как выбирать случайный стержень на каждом шаге, и так приведенной выше анализа вы получите О (п Л.Г. п) во время выполнения на ожидания , Для (b), если вы знаете, что массив в основном отсортирован, то выбор медианного является хорошей стратегией. Причина в том, что если мы можем сказать, что каждый элемент «близок» к тому, где он должен быть в отсортированной последовательности, тогда вы можете сделать аргумент, что каждый выбранный вами стержень является хорошим стержнем, предоставляя вам O (n lg n) время выполнения, которое вы хотите. (Термин «довольно близко» не очень математически точен, но я думаю, что вы могли бы формализовать это без особых трудностей, если захотите).
Что касается (c) и (d), из двух, (d) является гарантией получения O (n lg n) при ожидании. Если вы детерминистически выбираете определенные элементы для использования в качестве опорных точек, ваш алгоритм будет уязвим к детерминированным последовательностям, которые могут дегенерировать его до O (n). На самом деле есть действительно интересная статья по этому поводу: «"A Killer Adversary for Quicksort" от McIlroy, которая описывает, как вы можете взять любую детерминированную быструю сортировку и построить для нее патологически наихудший вход, используя функцию злонамеренного сравнения. Вы почти наверняка хотите избежать этого при любой реальной реализации quicksort, поскольку в противном случае злонамеренные пользователи могут запускать DoS-атаки на ваш код, подавая эти последовательности убийц, чтобы заставить вашу программу сортироваться в квадратичное время и, следовательно, зависать. С другой стороны, поскольку (d) случайно выбирает свои выборочные точки, он не уязвим для этой атаки, потому что в любой последовательности выбор опорных точек является случайным.
Интересно, что для (d), хотя не мешает выбрать три случайных элемента и взять медианную, вам не нужно это делать. Раннее доказательство достаточно, чтобы показать, что вы получите O (n lg n) при ожидании с помощью одного случайного выбора. На самом деле я не знаю, будет ли сбор медианы трех случайных значений улучшать производительность алгоритма быстрой сортировки, хотя, поскольку quicksort всегда Ω (n lg n), это, конечно, не будет асимптотически лучше, чем просто выбор случайных элементов, поскольку поворачивается.
Я надеюсь, что это немного поможет - мне очень нравится алгоритм быстрой сортировки и все проектные решения, связанные с созданием хорошей реализации быстрой сортировки. :-)
Непонятный вопрос. –
В: Для возможных стратегий, которые я выбрал (a-d), как они повлияют на общее поведение алгоритма quicksort? –