В Cormen упоминаются два метода разбиения быстрой сортировки:

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

а также:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i +1], A[r] )
return i + 1

Вне зависимости от метода выбора оси, в каких ситуациях одно предпочтительнее другого? Я знаю, например, что Lomuto сравнительно плохо преобразуется, когда высокий процент повторяющихся значений (т. Е. Где, скажем, более 2/3 массива - это одно и то же значение), где Hoare отлично работает в этой ситуации.

Какие другие особые случаи делают один метод разбиения значимым лучше, чем другой?

Педагогическое измерение

Из-за своей простоты метод разбиения Lomuto может быть проще в реализации. В « Жемчужине программирования» Джона Бентли о сортировке есть хороший анекдот :

«В большинстве обсуждений быстрой сортировки используется схема разбиения, основанная на двух приближающихся индексах [...] [то есть Хоаре]. Хотя основная идея этой схемы проста, я всегда находил детали хитрыми - однажды я провел большую часть двух дней, отыскивая ошибку, скрывающуюся в коротком цикле разбиения. Читатель предварительного проекта пожаловался, что стандартный двухиндексный метод на самом деле проще, чем метод Ломуто, и набросал некоторый код, чтобы подчеркнуть его; Я перестал смотреть после того, как нашел две ошибки.

Измерение производительности

Для практического использования простота реализации может быть принесена в жертву ради эффективности. Теоретически, мы можем определить количество сравнений элементов и обменов для сравнения производительности. Кроме того, на фактическое время работы будут влиять другие факторы, такие как производительность кэширования и неправильные прогнозы ветвлений.

Как показано ниже, алгоритмы ведут себя очень похоже на случайные перестановки, за исключением количества перестановок . Там Ломуто нужно в три раза больше, чем Хоаре!

Количество сравнений

$n-1$$n$

Количество свопов

Количество перестановок является случайным для обоих алгоритмов, в зависимости от элементов в массиве. Если мы предполагаем случайные перестановки , то есть все элементы различны, и каждая перестановка элементов одинаково вероятна, мы можем проанализировать ожидаемое количество перестановок .

$1,\ldots,n$

Метод Ломуто

$j$$A[j]$$x$$1,\ldots,n$$x-1$$x$$x-1$$x$

$\{1,\ldots,n\}$$\frac1n$

$n$

Метод Хоара

$x$

$i$$j$$x$$i$$j$

$x$

$\mathrm{Hyp}(n-1,n-x,x-1)$$n-x$$x-1$$(n-x)(x-1)/(n-1)$$x$

Наконец, мы снова усредняем значения по всем опорным точкам, чтобы получить общее ожидаемое количество перестановок для разбиения Хоара:

(Более подробное описание можно найти в моей магистерской диссертации , стр. 29.)

Шаблон доступа к памяти

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

Равные элементы и уже отсортированные списки

Как уже упоминалось в Wandering Logic, производительность алгоритмов отличается более резко для списков, которые не являются случайными перестановками.

$n/2$

$0$$i$$j$$\mathcal O(n\log n)$

$0$A[j] <= x$i=n$$\Theta(n^2)$

Заключение

Метод Ломуто прост и проще в реализации, но его не следует использовать для реализации метода сортировки библиотеки.

Некоторые комментарии добавлены к отличному ответу Себастьяна.

Я собираюсь рассказать об алгоритме перестановок разделов в целом, а не о его конкретном использовании для быстрой сортировки .

стабильность

Алгоритм Ломуто полустабилен : сохраняется относительный порядок элементов, не удовлетворяющих предикату . Алгоритм Хоара нестабилен.

Шаблон доступа к элементу

Алгоритм Lomuto может использоваться с односвязным списком или аналогичными структурами данных только для пересылки. Алгоритм Хоара требует двунаправленности .

Количество сравнений

$n-1$$n$

Но чтобы сделать это, мы должны пожертвовать 2 свойствами:

1. Последовательность для разделения не должна быть пустой.
2. Алгоритм не может вернуть точку разбиения.

$n$