Правильность перегородки Hoare

Разделение Hoare, как указано в 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

при использовании этого в быстрой сортировке, с {1,3,9,8,2,7,5} в качестве входных данных, после получения первого раздела {1,3,5,2,8,7,9}, что неверно поскольку все элементы, меньшие для поворота (здесь 5), должны быть на левой стороне. Может кто-то указать, что мне не хватает?

Источник

2 ответа

Решение

Алгоритм правильный. Вы разбиваете подмассив A[p..r] с помощью A[p] как стержень. Так что стержень 1 и не 5,

Hoare-Partition(A=[1,3,9,8,2,7,5], p=0, r=6)

результаты в:

x = A[p] = 1
i = -1
j = 7

repeat:
   j = j - 1 = 6; A[j] = 5
   j = j - 1 = 5; A[j] = 7
   j = j - 1 = 4; A[j] = 2
   ...
   j = j - 1 = 0; A[j] = 1
   A[j] == x
repeat:
   i = i + 1 = 0; A[i] = 1
   A[i] == x
if i < j
   i == j, therefore return j

В этом случае элементы не меняются местами.

Источник

У меня нет Cormen передо мной, но я уверен, что сравнение в первом цикле должно быть until A[j] < x - если это <=вы переместите элемент pivot в левую сторону и оставите его там (за которым следуют более мелкие элементы), что и произошло в вашем примере. Альтернативно, первое сравнение может быть <= а второй может быть > - просто убедитесь, что элемент pivot не будет "пойман" при обоих сравнениях.

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