Корректность Хоара раздела

Хоара раздела, как указана в 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), должны быть с левой стороны. Может ли кто-нибудь указать на то, что мне не хватает?

источник

2015-03-03 hm5

Почему инициализируется 'i' на 1 * меньше * чем индекс раздела? –

Где находится этот псевдокод? – templatetypedef

@ScottHunter: поскольку циклы _repeat..until_ loop, поэтому они будут выполнять одну итерацию перед проверкой состояния. Поэтому 'i == p' во время проверки первого условия. –

Алгоритм правильный. Вы разбиваете подмассиву 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

В этом случае, ни один из элементов не меняются местами.

источник

2015-03-03 23:30:43 beaker

Спасибо, я взял последний элемент в качестве стержня. В этом случае раздел был неправильным. Разве мы не можем использовать одну и ту же логику, принимая в качестве последнего элемента опорную точку? – hm5

Конечно, вы можете использовать последний элемент как стержень, но вам придется изменить порядок обхода массива, теперь сканировании слева направо, и обратный все операции сравнения. Это очень специализированный алгоритм локального раздела, а не общий, который был бы полезен для тестирования различных стратегий выбора точек. – beaker

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

источник

2015-03-03 19:26:05

ответ

Смежные вопросы