QuickSort invariante 3 condições com loop invariante

Question

Ao estudar o QuickSort usando o livro "Introdução aos Algoritmos" por Cormen, Lazer, Rivest e Stein, eles descrevem para mostrar a correção, uma invariante deve manter os 3 estágios do loop, a inicialização, a manutenção e a rescisão. do loop.

Com base no Algoritmo a seguir, não entendo propriedades 1 e 2 abaixo:

Aqui está o algoritmo que estou referenciando:

Alguém pode me ajudar a entender as condições

1) Se $ p \ leq k \ leq i $ então $ a [k] \ leq x $

No algoritmo quando, por exemplo, $ P $ é $ 1 $ , não vai $ i $ ser $ 0 $ .... Como isso ocuparia, já que antes do loop para o loop, temos i = p-1 / p >.

2) Se $ i + 1 \ leq k \ leq j - 1 $ então $ a [k]> x $

No algoritmo, por exemplo, quando entramos pela primeira vez o loop para j= 1, então $ i $ seria 0 .... eu não t ver como isso funciona.

obrigado

Answer 1

.

Se $ p \ leq k \ leq i $ então $ a [k] \ leq x. $ No algoritmo quando, por exemplo, $ P $ é $ 1 $ , não vai $ i $ ser $ 0 $ .... Como isso ocuparia, já que antes do loop para o loop, temos i = p-1

embora, como você observou, $ i $ é sempre menor do que $ P $ no Início do loop, pode tornar-se maior porque a declaração " $ i= i + 1 $ " no loop pode ser executado. Uma vez $ i $ foi aumentado, para pelo menos $ k= p $ , temos a classe $ p \ le k \ le i $ .

Observe que quando $ p \ le i $ não segura, ou seja, quando não há $ K $ < / span> tal que $ p \ le k \ le i $ , a condição "se $ p \ leq k \ leq i $ então $ a [k] \ leq x $ "mantém automaticamente. (Lembre-se de que a proposição "se falsa, então qualquer coisa pode acontecer" é sempre verdadeira.) Para falsificar essa condição, temos que encontrar uma instância de $ (p, k, i) $ tal que $ p \ leq k \ leq i $ mas $ a [k] \ gt x $ < / span>.

Você deve ser capaz de descobrir o caso do segundo loop invariante agora.

Answer 2

Eu não estou com vontade de traçar um código rightnow, mas entendo que você começa com um [r]= x e termina com um [i]= x

(o pivô, que parece ser escolhido como o último elemento $ R $ no código determinado, atinge sua posição correta com o restante da lista que se apresenta)

-At um primeiro olhar, talvez o código tenha alguns erros, não há necessidade de troca nos colchetes, e a outra troca deve ser apostar um [R] e um [J] dentro da $ mais $