QUICK SORT .. hMm ...

QUICK SORT

Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi. Sehingga didalamnya telah terjadi proses Rekursif.

Proses :
Bilangan yang di dalam kurung merupakan pivot
Persegi panjang yang digambarkan dengan garis terputus-putus menunjukkan sublist.
i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang >= pivot.
j bergerak dari sudut kanan ke kiri sampai menemukan nilai yang <> dari pivot (15).
j Berhenti pada index ke-6 karena juga langsung mendapatkan nilai yang <> dari pivot.
j berhenti pada index k-5 menunjuk pada nilai yang < dari pivot.
Karena i < j maka data yang ditunjuk oleh i (pivot) ditukar dengan data yang ditunjuk oleh j sehingga menjadi :
2 10 8 3 15 22

Langkah 3 :







Proses yang sama seperti sebelumnya dilakukan terhadap 2 buah sublist yang baru (ditandai dengan persegi panjang dengan garis terputus-putus).


Atau dapat juga digambarkan dalam bentuk tree seperti di bawah ini dengan pivot yang ditandai dengan huruf tebal. Kemudian setelah terurut dibaca inorder.