Quicksort invariant 3 condizioni con loop invariante

Question

In studiare Quicksort usando il libro "Introduzione agli algoritmi" di Cormen, Seeteron, Rivest e Stein, descrivono per mostrare la correttezza, un invariante deve tenere per le 3 fasi del loop, l'inizializzazione, la manutenzione e la risoluzione del ciclo.

Sulla base del seguente algoritmo, non capisco le proprietà 1 e 2 di seguito:

Ecco l'algoritmo che sto facendo riferimento:

Qualcuno potrebbe aiutarmi a capire le condizioni

1) se $ p \ leq k \ leq i $ quindi $ a [k] \ leq x $ < / span>

nell'algoritmo quando ad esempio, $ p $ è $ 1 $ , non sarà $ i $ Be $ 0 $ .... Come sarebbe in attesa, dal momento che prima del ciclo abbiamo i = p-1 < / P >.

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

Nell'algoritmo, ad esempio, quando entriamo per la prima volta il loop per il ciclo e J= 1, quindi $ i $ sarebbe 0 .... Io don ' T Guarda come funziona.

Grazie

Answer 1

.

se $ p \ leq k \ leq i $ quindi $ a [k] \ leq x. $ . Nell'algoritmo quando ad esempio, $ p $ è $ 1 $ , non sarà $ i $ Be $ 0 $ .... Come sarebbe successo, dal momento che prima del ciclo abbiamo generatodicetagcode

Sebbene, come hai osservato, $ i $ è sempre più piccolo di $ p $ al Inizio del ciclo, potrebbe diventare più grande perché la dichiarazione " $ i= I + 1 $ " nel ciclo potrebbe essere eseguito. Una volta $ i $ è stato aumentato, per almeno $ k= p $ , abbiamo $ p \ le k \ le i $ .

Si noti che quando $ p \ le i $ non tiene, cioè quando non c'è $ k $ < / span> tali quella $ p \ le k \ le i $ , la condizione "se $ p \ leq k \ leq $ quindi $ A [k] \ leq x $ "Tiene automaticamente. (Ricorda che la proposta "Se falsa, allora qualcosa può accadere" è sempre vero.) Per falsificare quella condizione, dobbiamo trovare un'istanza di $ (P, K, I) $ tali quella $ p \ leq k \ leq I $ ma $ a [k] \ gt x $ < / span>.

Dovresti essere in grado di capire il caso del secondo loop invariante ora.

Answer 2

Non sono dell'umore della traccia di un rigido di codice, ma capisci che inizi con un [R]= x e termina con un [i]= x

(il perno, che sembra essere scelto come l'ultimo elemento $ R $ Nel codice specificato, raggiunge la sua posizione corretta con il resto dell'elenco viene parezionato)

-it Un primo sguardo Forse il codice ha alcuni errori, non è necessario alcun scambio nelle staffe, e l'altro scambio dovrebbe essere puntato a [R] e A [J] all'interno della $ Else $