Quicksort Invariant 3 Conditions avec la boucle invariante

Question

En étudiant QuickSort à l'aide du livre "Introduction aux algorithmes" de Cormen, Leiserson, Rivest et Stein, ils décrivent pour montrer l'exactitude, un invariant doit tenir les 3 étages de la boucle, l'initialisation, la maintenance et la résiliation de la boucle.

Basé sur l'algorithme suivant, je ne comprends pas les propriétés 1 et 2 ci-dessous:

Voici l'algorithme que je référencent:

Quelqu'un pourrait-il m'aider à comprendre les conditions

1) Si $ P \ LEQ K \ LEQ I $ Alors $ A [K] \ LEQ X $ < / span>

dans l'algorithme quand par exemple, $ p $ est 1 $ , ne classe="math-conteneur"> $ i $ être 0 $ 0 $ .... Comment cela serait-il tenu, depuis avant la boucle de la boucle de i = p-1 < / p>

2) si $ i + 1 \ leq k \ leq j - 1 $ thin $ A [k]> x $

Dans l'algorithme, par exemple, lorsque nous entrez d'abord la boucle pour la boucle, et j= 1, puis $ i $ serait 0 .... je n'ai pas t voir comment cela fonctionne.

merci

Answer 1

si $ p \ leq k \ leq i $ alors $ a [k] \ leq x. $ Dans l'algorithme quand par exemple, $ p $ est $ 1 $ , ne $ I $ être $ 0 $ .... Comment cela serait-il tenu, depuis avant la boucle de la boucle de Générique

Bien que, comme vous l'avez observé, $ i $ est toujours plus petit que $ p $ à la Début de la boucle, cela pourrait devenir plus grand parce que la déclaration " $ i= i + 1 $ " dans la boucle pourrait être exécutée. Une fois $ i $ a été augmenté, pour au moins $ k= p $ , nous avons $ p \ le k \ le $ .

Notez que lorsque $ p \ le i $ ne tient pas, c'est-à-dire quand il n'y a pas de $ K $ < / span> tel que $ p \ le k \ le i $ , la condition "si $ p \ leq k \ Leq i $ alors $ a [k] \ leq x $ "s'installe automatiquement. (Rappelons que la proposition "si faux, alors tout peut arriver" est toujours vrai.) Pour falsifier cette condition, nous devons trouver une instance de $ (p, k, i) $ tel que $ p \ leq k \ leq i $ mais $ a [k] \ gt x $ < / span>.

Vous devriez être capable de comprendre le cas de la deuxième invariative de boucle maintenant.

Answer 2

Je ne suis pas dans l'ambiance de traçage d'un code rightnow, mais comprenez que vous commencez avec un [r]= x et se termine par [i]= x

(le pivot, qui semble être choisi comme dernier élément $ R $ dans le code donné, atteint sa position correcte avec le reste de la liste get la paratie)

-À un premier coup d'œil peut-être que le code a des erreurs, il n'est pas nécessaire d'échanger des supports, puis l'autre échange doit être parié à [R] & A [J] à l'intérieur de la $ autre $