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

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.

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

$P(k)$$k < n$$P(n-1)$$P(n)$

Dowód, który opisujesz, jest znany jako zasada silnej indukcji matematycznej i ma formę

$P(n)$$n\in \{1, 2, \dotsc\}$

1. $P(1)$

2. $(\forall k < n \;[P(k)])\Longrightarrow P(n)$

$P(n)$$n\ge 1$

$n$$k$$n-k-1$

$k<n$$n-k-1<n$

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

Przypuszczam, że:

• $P(1)$
• $n > 1$$P(1),\ldots,P(n-1)$$P(n)$

$P(n)$$n \geq 1$

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:

$A$$n \geq 1$$A$$B$

1. $A$
2. $\pi_1,\ldots,\pi_n$$1,\ldots,n$$B[i] = A[\pi_i]$
3. $B[1] \leq B[2] \leq \cdots \leq B[n]$

$P(n)$

$A$$n \geq 1$$B$Quicksort(A, n)$B[1] \leq B[2] \leq \cdots \leq B[n]$

$n$$n = 1$$n > 1$$X,x,Y,y$Quicksort$x,y < n$

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].