Der Versuch, diesen Quicksort-Korrektheitsnachweis zu verstehen

10

Dieser Beweis ist ein Beweis durch Induktion und lautet wie folgt:

P (n) ist die Behauptung, dass "Quicksort jedes Eingabearray der Länge n korrekt sortiert".

Basisfall: Jedes Eingabearray der Länge 1 ist bereits sortiert (P (1) gilt)

Induktiver Schritt: Fix n => 2. Fixiere ein Eingabearray der Länge n.

Muss zeigen: Wenn P (k) für alle k <n gilt, gilt auch P (n)

Dann zeichnet er ein Array A, das um einen Pivot p verteilt ist. Also zeichnet er p und nennt den Teil des Arrays, der <p ist, als 1. Teil, und der Teil, der> p ist, ist der zweite Teil. Die Länge von Teil 1 = k1 und die Länge von Teil 2 ist k2. Durch den Korrektheitsnachweis der Partitionsunterroutine (früher bewiesen) wird der Drehpunkt p in der richtigen Position aufgewickelt.

Geben Sie hier die Bildbeschreibung ein

Durch induktive Hypothese: 1., 2. Teil werden durch rekursive Aufrufe korrekt sortiert. (Mit P (K1), P (k2))

Also: Nach rekursiven Aufrufen wird das gesamte Array korrekt sortiert.

QED

Meine Verwirrung : Ich habe große Probleme, genau zu sehen, wie dies die Richtigkeit beweist. Wir nehmen also an, dass P (k) tatsächlich für alle natürlichen Zahlen k <n gilt.

Die meisten Induktionsbeweise, die ich bisher gesehen habe, gehen ungefähr so: Beweisen Sie den Basisfall und zeigen Sie, dass P (n) => P (n + 1). Sie beinhalteten normalerweise auch eine Art algebraische Manipulation. Dieser Beweis scheint sehr unterschiedlich zu sein, und ich verstehe nicht, wie ich das Konzept der Induktion darauf anwenden soll. Ich kann etwas begründen, dass die Richtigkeit der Partition-Subroutine der Schlüssel ist. Die Begründung für die Richtigkeit lautet also wie folgt: Wir wissen, dass bei jedem rekursiven Aufruf das Array um einen Pivot aufgeteilt wird. Dieser Drehpunkt befindet sich dann in seiner rechtmäßigen Position. Dann wird jedes Subarray weiter um einen Drehpunkt verteilt, und dieser Drehpunkt befindet sich dann in seiner rechtmäßigen Position. Dies geht so lange weiter, bis Sie ein Subarray der Länge 1 erhalten, das trivial sortiert ist.

Aber dann nehmen wir nicht an, dass P (k) für alle k <n gilt ... wir ZEIGEN tatsächlich, dass dies der Fall ist (da die Partition-Subroutine immer ein Element in seine rechtmäßige Position bringt). Gehen wir nicht davon aus, dass P. (k) gilt für alle k

FrostyStraw
quelle
Was ist "QUE"? Meinten Sie "QED"? (das lateinische Quod Erat Demonstrandum, das kein Wort ab U enthält )
Bakuriu
1
Ich meinte tatsächlich QED. Ich glaube, meine Verwirrung hat dazu geführt, dass ich "WAS?" auf Spanisch
FrostyStraw

Antworten:

13

P(k)k<nP(n1)P(n)

Der von Ihnen beschriebene Beweis ist als Prinzip der starken mathematischen Induktion bekannt und hat die Form

P(n)n{1,2,}

  1. P(1)

  2. (k<n[P(k)])P(n)

P(n)n1

nknk1

k<nnk1<n

Rick Decker
quelle
2
P(1)n=1k<1,P(k)P(1)
Okay, um klar zu sein ... Wir gehen davon aus, dass P (k) für alle k <n gilt. Und die Art und Weise, wie wir zeigen, dass P (k) ==> P (n) (für alle k <n) ist, beruht auf der Kombination des Wissens, dass sich der Drehpunkt mit Sicherheit in seiner korrekten Position befindet, und auf der Annahme (der induktiven Hypothese) ), dass die linken und rechten Subarrays ebenfalls sortiert sind. Kombinieren Sie das mit dem Basisfall (in dem k = 1 <n ist) und der Beweis ist vollständig?
FrostyStraw
Nun, ich denke, es würde nicht ausreichen zu wissen, dass sich der Pivot in der richtigen Position befindet, aber auch, dass das rechte Subarray größer als der Pivot und das linke kleiner als
FrostyStraw
@ FrostyStraw Es ist chinesisches Flüstern.
Raphael
1
@ FrostyStraw Hehe, ich meinte die Beweisstrategie. :)
Raphael
7

Dieser Beweis basiert auf dem Prinzip der vollständigen Induktion :

Nehme an, dass:

  • P(1)
  • n>1P(1),,P(n1)P(n)

P(n)n1

Q(m)P(1) and P(2) and  and P(m)

Lassen Sie uns nun die vollständige Induktion verwenden, um zu beweisen, dass die folgende Version von Quicksort die Eingabe korrekt sortiert:

Quicksort(A, n)
    if n = 1 then:
        return
    else:
        let X[1...x] consist of all elements of A[2],...,A[n] which are at most A[1]
        let Y[1...y] consist of all elements of A[2],...,A[n] which are larger than A[1]
        call Quicksort(X, x)
        call Quicksort(Y, y)
        set A to the concatenation of X, A[1], Y

Hier A[1],...,A[n]ist das Eingabearray und nseine Länge. Die Aussage, die wir beweisen wollen, lautet wie folgt:

An1AB

  1. A
  2. π1,,πn1,,nB[i]=A[πi]
  3. B[1]B[2]B[n]

P(n)

An1BQuicksort(A, n)B[1]B[2]B[n]

nn=1n>1X,x,Y,yQuicksortx,y<n

X[1]X[2]X[x]Y[1]Y[2]Y[y]
XYX[x]A[1]<Y[1]
X[1]X[x]A[1]<Y[1]Y[y].
B[1]B[n]P(n)
Yuval Filmus
quelle
4

Der fehlende Teil des Arguments ist die Transitivität von '<' - dh die Eigenschaft, dass wenn a <b und b <c, dann a <c. Der Beweis, dass das endgültige Array sortiert ist, sieht ungefähr so ​​aus:

Sei A [i], A [j] Elemente der Array-Nachsortierung, wobei i <j ist. Dann folgt A [i] <A [j] aus einem der folgenden Platzierungsfälle (und es gibt keine anderen Fälle):

(a) i und j befinden sich in der ersten Partition - A [i] <A [j] folgt durch Rekursion / Induktion.

(b) i und j befinden sich in der zweiten Partition - A [i] <A [j] folgt durch Rekursion / Induktion.

(c) i befindet sich in der ersten Partition und j ist der Index des Pivots - A [i] <A [j] folgt der Nachweis der Partitionsprozedur.

(c) i ist der Index des Pivots und j befindet sich in der zweiten Partition - A [i] <A [j] folgt der Nachweis der Partitionsprozedur.

(e) i befindet sich in der ersten Partition und j befindet sich in der zweiten Partition - dann durch Partitionsprozedur A [i] <Pivot und Pivot <A [j]. Also durch Transitivität A [i] <A [j].

PMar
quelle