Próbuję zrozumieć ten dowód poprawności Quicksort

10

Ten dowód jest dowodem indukcyjnym i wygląda następująco:

P (n) jest twierdzeniem, że „Quicksort poprawnie sortuje każdą tablicę wejściową o długości n”.

Przypadek podstawowy: każda tablica wejściowa o długości 1 jest już posortowana (blokada P (1))

Krok indukcyjny: fix n => 2. Napraw niektóre tablice wejściowe o długości n.

Trzeba pokazać: jeśli P (k) utrzymuje się dla wszystkich k <n, to P (n) również

Następnie rysuje tablicę A podzieloną wokół części przestawnej p. Rysuje więc p i wywołuje część tablicy, która jest <p jako pierwsza część, a część, która jest> p, jest drugą częścią. Długość części 1 = k1, a długość części 2 wynosi k2. Dzięki potwierdzeniu poprawności podprogramu podziału (udowodnionym wcześniej) oś obrotu p kończy się we właściwej pozycji.

wprowadź opis zdjęcia tutaj

Według hipotezy indukcyjnej: 1., 2. części są poprawnie sortowane według wywołań rekurencyjnych. (Używając P (K1), P (k2))

Zatem: po wywołaniach rekurencyjnych cała tablica jest poprawnie sortowana.

CO BYŁO DO OKAZANIA

Moje zamieszanie : mam duży problem z tym, jak dokładnie to potwierdza. Zakładamy więc, że P (k) rzeczywiście obowiązuje dla wszystkich liczb naturalnych k <n.

Większość dowodów indukcyjnych, które do tej pory widziałem, idzie mniej więcej tak: Udowodnij przypadek podstawowy i pokaż, że P (n) => P (n + 1). Zazwyczaj dotyczyły one także pewnego rodzaju manipulacji algebraicznych. Ten dowód wydaje się bardzo różny i nie rozumiem, jak zastosować w nim koncepcję indukcji. Mogę poniekąd zrozumieć, że poprawność podprogramu Partycja jest kluczem. Oto uzasadnienie jego poprawności: Wiemy, że każde wywołanie rekurencyjne podzieli tablicę wokół osi przestawnej. Ten punkt obrotu będzie wtedy w prawidłowej pozycji. Następnie każda podtablica zostanie dodatkowo podzielona wokół osi obrotu, a następnie ta oś obrotu znajdzie się w prawidłowej pozycji. Trwa to tak długo, aż pojawi się podtablica o długości 1, która jest trywialnie posortowana.

Ale wtedy nie zakładamy, że P (k) obowiązuje dla wszystkich k <n .... w rzeczywistości POKAŻEM, że tak (ponieważ podprogram Partycji zawsze umieści jeden element na właściwej pozycji). Czy nie zakładamy, że P (k) trzyma dla wszystkich k

FrostyStraw
źródło
Co to jest „QUE”? Miałeś na myśli „QED”? ( Demonstrandum Latin Quod Erat, które nie zawiera żadnego słowa rozpoczynającego się na U )
Bakuriu,
1
Naprawdę miałam na myśli QED. Myślę, że moje zamieszanie doprowadziło mnie do napisania „CO?” po hiszpańsku
FrostyStraw

Odpowiedzi:

13

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

Dowód, który opisujesz, jest znany jako zasada silnej indukcji matematycznej i ma 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
źródło
2
P(1)n=1k<1,P(k)P(1)
Okej więc ... żeby być jasnym ... PRZYJMUJEMY P (k) jest prawdziwe dla wszystkich k <n. Sposób, w jaki POKAZAMY, że P (k) ==> P (n) (dla wszystkich k <n) polega na połączeniu wiedzy o tym, że oś na pewno będzie we właściwej pozycji, oraz poprzez założenie (hipoteza indukcyjna ), że lewe i prawe podrzędne są również posortowane. Połącz to z przypadkiem podstawowym (w którym k = 1 <n), a dowód jest kompletny?
FrostyStraw
Cóż, myślę, że nie wystarczy wiedzieć, że oś jest we właściwej pozycji, ale także, że prawa podstawa jest większa niż oś, a lewa jest mniejsza niż
FrostyStraw
@FrostyStraw To chińskie szepty.
Raphael
1
@FrostyStraw Hehe, miałem na myśli strategię dowodu. :)
Raphael
7

Ten dowód wykorzystuje zasadę całkowitej indukcji :

Przypuszczam, że:

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

P(n)n1

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

Teraz zastosujmy pełną indukcję, aby udowodnić, że następująca wersja Quicksort poprawnie sortuje dane wejściowe:

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

Oto A[1],...,A[n]tablica wejściowa i njej długość. Oświadczenie, które chcemy udowodnić, jest następujące:

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
źródło
4

Brakującą częścią argumentu jest przechodniość „<” - tj. Właściwość, że jeśli a <b i b <c, to a <c. Dowód, że końcowa tablica jest posortowana, wygląda mniej więcej tak:

Niech A [i], A [j] będą elementami post-sortowania tablicy, gdzie i <j. Następnie A [i] <A [j] wynika z jednego z następujących przypadków umieszczania (i nie ma innych przypadków):

(a) i i j znajdują się w pierwszej partycji - A [i] <A [j] następuje przez rekurencję / indukcję.

(b) i i j znajdują się w drugiej części - A [i] <A [j] następuje przez rekurencję / indukcję.

(c) i znajduje się w pierwszej przegrodzie, a j jest indeksem osi przestawnej - A [i] <A [j] następuje po procedurze potwierdzenia podziału.

(c) i jest indeksem osi obrotu, zaś j znajduje się w drugiej przegrodzie - A [i] <A [j] następuje po procedurze potwierdzenia podziału.

(e) i znajduje się na pierwszej partycji, a j na drugiej partycji - następnie według procedury partycji A [i] <pivot i pivot <A [j]. Zatem przez przechodniość A [i] <A [j].

PMar
źródło