Как изменить схему разделов Lomuto?

Question

Lomuto partition - простой алгоритм разбиения, используемый в быстрой сортировке. Алгоритм Lomuto разделяет подрешетку A[left] ... A[right] и предполагает, что A[left] является точкой разворота. Как изменить этот алгоритм для разбиения A[left] ... A[right] с использованием заданного pivot P (который отличается от A[left])?

Answer 1

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

Использование произвольного значения для сводной точки (скажем, что-то не в подмассиве) может привести к путанице в реализации быстрой сортировки, поскольку не будет никакой гарантии, что ваш раздел создал проблемунемного меньше.Скажем, у вас было ноль в качестве значения, на которое вы поворачивались, но все записи массива N были положительными.Тогда ваш раздел даст массив нулевой длины элементов <= 0 и массив длины N, содержащий элементы> = 0 (что все они).В этом случае вы получите бесконечный цикл, пытаясь выполнить быструю сортировку.То же самое, если вы пытались найти медиану массива, используя эту измененную форму раздела Lomuto.Раздел решающим образом зависит от выбора элемента из массива для разворота.Вы в основном потеряете постусловие, что элемент (ось) будет исправлен на месте после раздела, что гарантирует раздел Lomuto.

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

Вы можете повернуть другой объектэлемент массива путем замены его на первый (или последний, если вы реализуете его таким образом) элемент в качестве первого шага.Посмотрите видео-лекцию MIT по быстрой сортировке для курса 6.046J, где подробно рассматриваются алгоритм разделения Lomuto (хотя они просто называют его разделением) и ванильная реализация быстрой сортировки на его основе, не говоря уже о большой вероятности обсуждения ожидаемого времени выполнениярандомизированная форма быстрой сортировки:

http://www.youtube.com/watch?v=vK_q-C-kXhs

У CLRS и Pearls Programming есть отличные разделы по быстрой сортировке, если, возможно, вы застряли, используя подчиненную книгу для класса алгоритмов или чего-то еще.

Answer 2

зависит от того, как вы определяете P, P является индексом или конкретным элементом?если это индекс, то это легко.Вы изменяете свои два прохода

...
i = left
j = right
while (a[i]<a[p]) i++
while (a[p]>a[j]) j--
if (i <= j)
    swap(a, i, j)
    qsort(a, left,i)
    qsort(a, j,right)
...

, если P не индекс, а конкретное значение, тогда вам нужно будет сначала найти его, и только потом делать то же самое с полученным индексом.Поскольку массив еще не отсортирован, вы можете искать только линейно.Вы могли бы также придумать более умную схему (хеш-таблицу) для нахождения своего стержня P, но я не понимаю, почему вам нужно было бы сделать такую ​​вещь.