Объяснение алгоритма разбиения Hoare

Согласно псевдокоду, приведенному на многих сайтах, я написал это Hoare алгоритм секционирования, который принимает массив, начальный и конечный индексы подмассива, подлежащего разделению, на основе заданной оси. Он работает нормально, но может кто-нибудь объяснить логику, как он делает то, что делает? Вот код:

def hoare(arr,start,end):
     pivot = 4
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     return j

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

Источник

2 ответа

Решение

Я бы предложил смоделировать это, используя колоду карт и две пешки / монеты, чтобы представить i а также j, По сути, алгоритм выполняет эти две вещи одновременно:

  • Найдите, где массив должен быть разделен, чтобы иметь правильное количество "сегментов" слева и справа от этой позиции. Это делается с помощью значений i а также j встреча в "середине" раздела.
  • Переместите элементы массива влево или вправо от середины, в зависимости от того, меньше они или больше, чем опорная точка.

Это означает, что в любое время i находится либо посередине, либо слева от него. Обратное утверждение верно для j, Зная это, можно увидеть, что while Циклы делают, это найти элемент, который находится слева от середины, но должен быть справа, и наоборот. То есть найдите два элемента, которые находятся не в той половине. Затем они меняются местами.

когда i а также j встретиться в середине, слева у вас есть элементы, которые были пропущены whileпотому что они меньше, чем pivot; или элементы, которые были обменены с другой стороны, и, следовательно, также меньше, чем pivot, (Наоборот для элементов справа от середины.)

Возможный источник путаницы заключается в том, что можно считать, что индекс массива, начинающийся с нуля, либо указывает на элемент, либо указывает между двумя элементами. Например, индекс 0 в основном означает "между нулем и первым элементом в массиве", и когда вы обращаетесь к элементу, вы выбираете тот, который следует за этой позицией - создание array[0] результат в том, что интуитивно первый элемент массива.

Источник

И Hoare, и Lamuto являются алгоритмами разбиения. Алгоритм разбиения перемещает объекты в массиве так, что все, что меньше определенного элемента, оказывается на одной стороне, а все больше на другой. Это может быть использовано для быстрой сортировки массива или для поиска медианы.

Hoare работает, перемещая две границы к середине, одну слева и одну справа. Следующие шаги выполняются в цикле:

  1. Левая граница перемещается, пока не достигнет чего-то большего, чем выбранный элемент.
  2. Правая граница перемещается, пока не достигнет чего-то меньшего, чем выбранный элемент.
  3. Если границы не пересеклись, они меняются местами.

Этот процесс повторяется до тех пор, пока границы не встретятся посередине. В результате получается раздел со всем меньшим слева и всем большим справа.

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

Источник
Другие вопросы по тегам