Разделение быстрой сортировки: Hoare vs. Lomuto

83

В 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 отлично работает в этой ситуации.

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

Роберт С. Барнс
источник
2
Я не могу думать о любой ситуации , в которой Lomuto лучше , чем Хоара. Кажется, Ломуто выполняет дополнительные перестановки всякий раз A[i+1] <= x. В отсортированном массиве (и с учетом разумно выбранных опорных точек) Хоар почти не меняет местами, а Ломуто делает тонну (как только j становится достаточно маленьким, тогда все A[j] <= x.) Чего мне не хватает?
Блуждающая логика
2
@WanderingLogic Я не уверен, но кажется, что решение Кормена использовать раздел Lomuto в его книге может быть педагогическим - кажется, что он имеет довольно простой инвариант цикла.
Роберт С. Барнс
2
Обратите внимание, что эти два алгоритма не делают одно и то же. В конце алгоритма Хоара пивот не на своем последнем месте. Вы можете добавить a swap(A[p], A[j])в конце Hoare, чтобы получить одинаковое поведение для обоих.
Орелиен Оомс
Вы также должны проверить i < jв 2 повторных циклах разбиения Хоара.
Орелиен Оомс
@ AurélienOoms Код скопирован прямо из книги.
Роберт С. Барнс

Ответы:

92

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

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

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

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

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

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

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

n1n

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

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

1,,n

Метод Ломуто

jA[j]x1,,nx1xx1x

{1,,n}1n

1nx=1n(x1)=n212.

n

Метод Хоара

x

ijxij

x

Hyp(n1,nx,x1)nxx1(nx)(x1)/(n1)x

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

1nx=1n(nx)(x1)n1=n613.

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

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

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

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

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

n/2

0ijO(nlogn)

0A[j] <= xi=nΘ(n2)

Заключение

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

Себастьян
источник
16
Вау, это один подробный ответ. Красиво сделано!
Рафаэль
Должен согласиться с Рафаэлем, действительно хороший ответ!
Роберт С. Барнс
1
Я хотел бы сделать небольшое пояснение, что, поскольку отношение уникальных элементов к общему количеству элементов становится меньше, число сравнений, которые делает Ломуто, растет значительно быстрее, чем сравнения Хоара. Вероятно, это связано с плохим разделением со стороны Ломуто и хорошим средним разделением со стороны Хоара.
Роберт С. Барнс
Отличное объяснение двух методов! Спасибо!
v kouk
Вы можете легко создать вариант метода Lomuto, который может извлечь все элементы, равные оси, и исключить их из рекурсии, хотя я не уверен, поможет ли это или помешает усредненному случаю.
Якуб Наребски
5

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

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

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

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

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

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

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

n1n

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

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

n

Фернандо Пелличчиони
источник