Jelaskan Versi Sederhana dari Quicksort

Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:

return 'array'  // an array of zero or one elements is already sorted

select and remove a pivot value 'pivot' from 'array'

create empty lists 'less' and 'greater'

for each 'x' in 'array'

if 'x' ≤ 'pivot' then append 'x' to 'less'

else append 'x' to 'greater'

return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk Sorting Pembandingan. Jenis ini juga merupakan jenis sorting yang stabil (asumsikan bahwa untuk setiap method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama).

Kebenaran dari algoritme partisi didasari pada dua argumen berikut:

Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot (Invarian Loop).

Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritme tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritme akan menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih besar dari nya, data ini sendiri akan diurutkan secara hipotesis rekursif.