Mencoba memahami bukti Koreksi Quicksort ini

Bukti ini adalah bukti melalui induksi, dan berlaku sebagai berikut:

P (n) adalah pernyataan bahwa "Quicksort dengan benar mengurutkan setiap larik input dengan panjang n."

Kasus dasar: setiap larik input dengan panjang 1 sudah diurutkan (P (1) berlaku)

Langkah induktif: fix n => 2. Perbaiki beberapa larik input dengan panjang n.

Perlu ditunjukkan: jika P (k) berlaku untuk semua k <n, maka P (n) juga berlaku

Dia kemudian menggambar array A yang dipartisi di sekitar pivot p. Jadi dia menggambar p, dan memanggil bagian dari array yang <p sebagai bagian 1, dan bagian yang> p adalah bagian kedua. Panjang bagian 1 = k1, dan panjang bagian 2 adalah k2. Dengan bukti ketepatan subrutin Partition (dibuktikan sebelumnya), pivot p berakhir pada posisi yang benar.

Dengan hipotesis induktif: Bagian ke-1 disortir dengan benar oleh panggilan rekursif. (Menggunakan P (K1), P (k2))

Jadi: setelah panggilan berulang, seluruh array diurutkan dengan benar.

QED

Kebingungan saya : Saya memiliki banyak masalah dalam melihat dengan tepat bagaimana ini membuktikan kebenarannya. Jadi kita mengasumsikan bahwa P (k) memang berlaku untuk semua bilangan alami k <n.

Sebagian besar bukti induksi yang telah saya lihat sejauh ini seperti: Buktikan kasus dasar, dan tunjukkan bahwa P (n) => P (n +1). Mereka biasanya juga melibatkan semacam manipulasi aljabar. Bukti ini tampaknya sangat berbeda, dan saya tidak mengerti bagaimana menerapkan konsep Induksi ke sana. Saya agak dapat beralasan bahwa kebenaran subrutin Partisi adalah kuncinya. Jadi adalah alasan untuk kebenarannya sebagai berikut: Kita tahu bahwa setiap panggilan rekursif, ia akan mempartisi array di sekitar pivot. Pivot ini akan berada pada posisi yang seharusnya. Kemudian setiap subarray akan dipartisi lebih lanjut di sekitar pivot, dan pivot itu kemudian akan berada di posisi yang seharusnya. Ini akan terus berlanjut sampai Anda mendapatkan subarray dengan panjang 1, yang disortir secara sepele.

Tetapi kemudian kita tidak berasumsi bahwa P (k) berlaku untuk semua k <n .... kita benar-benar MENUNJUKKAN itu terjadi (karena subrutin Partisi akan selalu menempatkan satu elemen dalam posisi yang selayaknya.) Apakah kita tidak berasumsi bahwa P (k) (k) berlaku untuk semua k

Kita memang mengasumsikan berlaku untuk semua . Ini adalah generalisasi dari gaya bukti "From , kami membuktikan " yang Anda kenal.k < n P ( n - 1 ) P ( n $P(k)$$k < n$$P(n-1)$$P(n)$

Bukti yang Anda gambarkan dikenal sebagai prinsip induksi matematika yang kuat dan memiliki bentuk

Misalkan adalah predikat yang ditentukan pada . Jika kita bisa menunjukkan itun ∈ { 1 , 2 , ... $P(n)$$n\in \{1, 2, \dotsc\}$

1. $P(1)$ benar, dan

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

Maka benar untuk semua bilangan bulat$P(n)$ .$n\ge 1$

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

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

Bukti ini menggunakan prinsip induksi lengkap :

Seandainya:

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

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

Sekarang, mari kita gunakan induksi lengkap untuk membuktikan bahwa versi Quicksort berikut mengurutkan inputnya dengan benar:

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

Berikut A[1],...,A[n]adalah array input, dan npanjangnya. Pernyataan yang ingin kami buktikan adalah sebagai berikut:

$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$

Bagian yang hilang dari argumen adalah transitivitas '<' - yaitu properti yang jika a <b dan b <c, maka a <c. Bukti bahwa array terakhir diurutkan berjalan seperti ini:

Biarkan A [i], A [j] menjadi elemen dari array post-sort, di mana saya <j. Kemudian A [i] <A [j] mengikuti dari salah satu case penempatan berikut (dan tidak ada case lain):

(a) i dan j berada di partisi pertama - A [i] <A [j] diikuti oleh rekursi / induksi.

(B) i dan j berada di partisi kedua - A [i] <A [j] diikuti oleh rekursi / induksi.

(c) i ada di partisi pertama dan j adalah indeks pivot - A [i] <A [j] diikuti oleh bukti prosedur partisi.

(c) i adalah indeks pivot dan j berada di partisi kedua - A [i] <A [j] diikuti oleh bukti prosedur partisi.

(e) i ada di partisi pertama dan j ada di partisi kedua - kemudian dengan prosedur partisi, A [i] <pivot, dan pivot <A [j]. Jadi dengan transitivitas, A [i] <A [j].