Уточнить критерии обмена в быстрой сортировке?

Question

В быстрой сортировке идея состоит в том, чтобы вы продолжали выбирать опору. И вы меняете значение, которое вы найдете слева, которое больше, чем пивот, на значение, которое вы найдете справа, которое меньше, чем шарнир. смотри: ref

Просто хочу быть на 100% уверенным в том, что происходит в следующих случаях:

• Нет значения слева больше, чем шарнир, значение справа меньше, чем шарнир
• Значение слева больше, чем шарнир, нет значения справа меньше, чем шарнир
• Нет значения слева больше, чем шарнир, нет значения справа меньше, чем шарнир

Answer 1

Критерии обмена зависят от реализации. То, что происходит в трех упомянутых вами случаях, зависит от схемы разбиения. Существует множество реализаций Quicksort, но две наиболее известные из них (на мой взгляд):

• Раздел Хоара: первый элемент - это стержень и две индексные переменные (i а также j) пройти массив (a[]) к центру, в то время как элементы, с которыми они сталкиваются, меньше / больше, чем точка поворота. затем a[j] а также a[i] поменялись местами. Обратите внимание, что в этой реализации своп происходит для элементов, которые равны стержню. Это считается важным, когда ваш массив содержит много одинаковых записей. После i а также j пересекать, a[0] поменялся местами с a[j]Таким образом, стержень находится между разделом с меньшим или равным разделом и разделом с большим или равным значением.

• Раздел Ломуто. Это тот, который реализован в псевдокоде в текущей записи быстрой сортировки Wiki в разделе " Версия на месте". Здесь пивот может быть чем угодно (скажем, медиана или медиана трех) и поменяется местами с последним элементом a, Здесь только i "идет" к концу массива: всякий раз, когда a[i]>=pivot он поменялся с a[j] а также j уменьшается. В конце, пивот меняется на a[i+1]

(Смотрите здесь, например, для иллюстрации).

Роберт Седжвик представляет трехстороннюю схему разбиения, где массив делится на три раздела: меньше, равно и больше, чем сводная точка: утверждается, что он имеет лучшую производительность для массивов с большим количеством дупликов или идентичных значений. Это реализовано еще по-другому (см. Ссылку выше).

Answer 2

В то время как выбор значения поворота важен для производительности, он не важен для сортировки.

После того, как вы выбрали какое-либо значение в качестве точки поворота, вы перемещаете все значения, меньшие или равные точке поворота, влево от точки поворота, а справа от нее вы получаете все значения, превышающие эту точку поворота.

После всех этих движений значение разворота находится в своей окончательной позиции.

Затем вы рекурсивно повторите вышеописанную процедуру для подмассива слева от значения pivot, а также для подмассива справа от него. Или, конечно, если подмассивы содержат 0 или 1 элемент, они не имеют ничего общего с сортировкой.

Таким образом, в итоге вы выбираете кучу значений разворота, которые после всех ходов попадают в свои конечные позиции. Между этими сводными значениями находятся пустые или одноэлементные подмассивы, которые не нуждаются в сортировке, как описано ранее.