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

Question

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

Answer 1

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

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

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

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

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

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

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 не является индексом, но конкретное значение, то вам нужно будет искать для него первым, и только потом делать выше с результирующим показателем. Поскольку массив еще не отсортирован, вы можете искать только линейно. Вы могли бы также придумать более умную схему (хеш-таблицу) для поиска вашего Pivot P, но я не понимаю, зачем вам нужно это делать.