Перегородка Хоара против Ломуто

Question

Можете ли вы привести пример, что схема с двумя разделами дает другой результат?Для Lomuto мы должны написать:

quicksort(A,l,p)
quicksort(A,p+1,h)

В то время как для Hoare:

quicksort(A,l,p+1)
quicksort(A,p+1,h)

(Операции выполняются в [low, high))

Какая разница?

Answer 1

Чтобы понять разницу, мы также должны сосредоточиться на методе partition, а не только на вызовах quicksort.

Схема разбиения Lomuto :

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi - 1 do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

Схема разбиения Hoare :

algorithm partition(A, lo, hi) is
    pivot := A[lo + (hi - lo) / 2]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

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

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

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

Комментарий, если у вас есть какие-либо дополнительные сомнения, и мы поможем вам разрешить сомнения.

Answer 2

Базовая схема секционирования Lomuto меняет стержень в стороне, делает раздел, заменяет стержень на место и затем возвращает индекс в стержень в его отсортированной позиции. В этом случае сводку можно исключить из рекурсивных вызовов:

Базовая схема разбиения Hoare сканирует с обоих концов в направлении некоторой точки внутри перегородки, располагая все элементы, меньшие, чем точка поворота, слева от всех элементов, превышающих точку поворота, но все элементы, равные точке поворота, включая саму точку поворота, может заканчиваться где угодно в разделе, и возвращаемый индекс является точкой разделения между левым (элементы <= pivot) и правым (elements> = pivot), поэтому вызывающий код не может исключить элемент в индексе, возвращенном из функции разделения Hoare от рекурсивных звонков. Если схема Hoare модифицирована, чтобы быть похожей на Lomuto, где она меняет сводную точку на любой конец, выполняет разделение, а затем заменяет сводную точку на индекс разделения, тогда вызывающий код может исключить сводную точку, но в конечном итоге это происходит медленнее.

Answer 3

Разница между этими разделами не в рекурсивных вызовах.

Действительно любой раздел (поддерживающий правильный интерфейс) может использоваться с той же реализацией основной подпрограммы.

Функция разбиения обычно возвращает индекс точки разворота. Этот стержень уже стоит на последнем месте. Нет необходимости снова обрабатывать этот индекс.

Так что для случая, когда low включено в лечение, но high нет, мы можем написать

    pivotindex = partition(arr, low, high); 

    // Separately sort elements before pivotindex and after pivotindex

    quickSort(arr, low, pivotindex); 
    quickSort(arr, pivotindex + 1, high);