Quicksort invariante 3 condiciones con bucle invariante

Question

Al estudiar Quicksort utilizando el libro "Introducción a los algoritmos" por Cormen, Leabloson, Rivest y Stein, describen para mostrar la exactitud, un invariante debe mantener las 3 etapas del bucle, la inicialización, el mantenimiento y la terminación. del bucle.

Basado en el siguiente algoritmo, no entiendo las propiedades 1 y 2 a continuación:

Aquí está el algoritmo que estoy haciendo referencia:

¿Podría alguien ayudarme a entender las condiciones

1) Si $ P \ leq k \ leq i $ luego $ a [k] \ leq x $ < / span>

En el algoritmo cuando, por ejemplo, $ p $ es $ 1 $ , no $ i $ Be $ 0 $ .... ¿cómo se llevaría a cabo, desde antes del bucle para el bucle, tenemos i = p-1? / p>

2) Si $ i + 1 \ leq k \ leq j - 1 $ luego $ a [k]> x $

En el algoritmo, por ejemplo, cuando ingresamos primero al bucle For, y J= 1, luego $ i $ sería 0 ... yo no T ver cómo funciona esto.

gracias

Answer 1

Si $ P \ leq k \ leq i $ luego $ a [k] \ leq x. $ En el algoritmo cuando, por ejemplo, $ p $ es $ 1 $ , no $ i $ be $ 0 $ .... ¿Cómo se mantuvo esto, desde antes del bucle para el bucle, tenemos i = p-1

Aunque, como ha observado, $ i $ es siempre más pequeño que $ P $ en el Inicio del bucle, puede volverse más grande porque la declaración " $ i= i + 1 $ " en el bucle podría ser ejecutado. Una vez $ i $ se ha incrementado, para al menos $ k= p $ , tenemos $ P \ le k \ le i $ .

Tenga en cuenta que cuando $ P \ le i $ no se mantiene, es decir, cuando no hay $ k $ < / span> tal que $ P \ le k \ le i $ , la condición "Si $ P \ leq k \ leq i $ luego $ a [k] \ leq x $ "se mantiene automáticamente. (Recordemos que la proposición "Si falsa, entonces todo puede suceder" siempre es cierta). Para falsificar esa condición, tenemos que encontrar una instancia de $ (p, k, i) $ de tal manera que $ P \ leq k \ leq i $ pero $ a [k] \ gt x $ < / span>.

Debe poder descubrir el caso del segundo bucle invariante ahora.

Answer 2

No estoy de humor para rastrear un código RightNow, pero entienda que comienza con un [R]= X y termina con un [I]= X

(El pivote, que parece ser elegido como el último elemento $ r $ en el código dado, llega a su posición correcta con el resto de la lista.)

-at Una primera mirada, tal vez el código tiene algunos errores, no hay necesidad de intercambio en los paréntesis, y el otro intercambio debe apostarse a [R] & A [J] dentro de la $ más $