QuickSort Invariante 3-Bedingungen mit Schleifen invariant

Question

beim Studium des Quicksorts mit dem Buch "Einführung in Algorithmen" von Cormmen, Leiser, Leisers, Rivest und Stein, beschreiben sie, um Richtigkeit zu zeigen, ein Invariante muss für die drei Stufen der Schleife, die Initialisierung, die Wartung und die Kündigung halten der Schleife.

Basierend auf dem folgenden Algorithmus verstehe ich keine Eigenschaften 1 und 2 unten:

Hier ist der Algorithmus, den ich verweist:

"

könnte mir jemand helfen, den Bedingungen zu verstehen

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

im Algorithmus, wenn zum Beispiel $ P $ $ 1 $ , nicht $ i $ Seien Sie $ 0 $ ... Wie würde dies festhalten, da vor der für Schleife GROSSACDICETAGCODE < / p>

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

im Algorithmus Zum Beispiel, wenn wir zum ersten Mal die für Schleife eingeben, und J= 1, dann wäre $ I $ 0 .... ich nicht Ich sehe, wie das funktioniert.

danke

Answer 1

wenn $ p \ leq k \ leq i $ dann $ a [k] \ leq x. $ Im Algorithmus ist beispielsweise $ P $ $ 1 $ , nicht $ i $ Seien Sie $ 0 $ .... Wie würde dies festhalten, da wir vor der für Schleife generakodicetagcode

haben?

, obwohl Sie beobachtet haben, ist $ i $ immer kleiner als $ P $ bei der Beginn der Schleife, es könnte größer werden, da die Anweisung " $ i= i + 1 $ " in der Schleife ausgeführt werden konnte. Sobald $ I $ erhöht wurde, wurde zumindest $ k= P $ , wir haben $ p \ le k \ le i $ .

Beachten Sie, dass, wenn $ p \ le i $ nicht hält, dh wenn kein $ k $ vorhanden ist < / span> so, dass $ p \ le k \ le i $ , die Bedingung ", wenn $ p \ leq k \ leq) I $ dann $ a [k] \ leq x $ "Hält automatisch. (Erinnern Sie sich daran, dass der Vorschlag "Wenn false, dann passieren kann, ist alles immer wahr.) Um diesen Zustand zu fälschen, müssen wir eine Instanz von $ (P, K, I) $ finden so, dass $ p \ leq k \ leq i $ aber $ a [k] \ gt x $ < / span>.

Sie sollten jetzt den Fall der zweiten Schleife invariant herausfinden können.

Answer 2

Ich bin nicht in der Stimmung, einen Code Rightnow zu verfolgen, sondern zu verstehen, dass Sie mit einem [R]= x und endet mit einem [i]= x

enden

(der Drehzapfen, der als das letzte Element $ R $ in dem angegebenen Code gewählt zu sein scheint, erreicht die korrekte Position mit dem Rest der Liste abgestimmt)

-at Ein erster Blick Vielleicht, vielleicht hat der Code einige Fehler, es ist nicht erforderlich, dass der Austausch in den damaligen Klammern erforderlich ist, und der andere Austausch sollte ein Wetten A [R] & A [J] in der $ 40 $