Memahami Quick Sort Step By Step

Quicksort yaitu salah satu algoritma pengurutan yang paling sering digunakan. Mengapa ? Karena memang quicksort sendiri mempunyai kecepatan yang cukup untuk mengurutkan banyak sekali macam data. Namun bagi para programmer yang masih newbie dan masih kesulitan dalam memahami algoritma ini, maka Anda sangat sempurna apabila membaca postingan ini.

Sebelumnya, saya beri tahu, bahwa Quicksort mempunyai macam-macam variasi. Nah jadi jangan gundah kalo liat di youtube cara quicksortnya beda-beda.. haha.. Memang banyak sekali variasi. Nah kali ini saya akan ajarkan salah satu variasi quicksort saja.


Oke, eksklusif saja kita mulai

Tutorial Quicksort Step By Step

Semisal kita mempunyai data ibarat ini :

12 90 23 45 13 43 11 44

Pertama, tentukan pivot. Pivot yaitu salah satu penanda ibarat index. Lalu beri juga tanda berjulukan left dan right. Saya singkat L dan R, sedangkan pivot saya singkat P.
Pivot akan saya set di index pertama

12 90 23 45 13 43 11 44
L                                 R
P

Lalu cek apakah R lebih kecil dari P. (Jika R yang bergeser maka cek apakah lebih kecil, tapi kalau L yang bergeser maka cek apakah lebih besar dari P)
44 < 12 ? Tidak ! geser ke kiri lagi
12 90 23 45 13 43 11 44
L                            R
P
11 < 12 ? Iya ! Tukar posisi yaitu 12 dan 11. Pada ketika penukaran, pivot ikut bertukar menjadi R.
11 90 23 45 13 43 12 44
L                            R
                              P
Setelah itu, sebab P berada di R, maka L berjalan ke kanan, dan kalau ada angka yang lebih besar, maka berhenti dan lakukan penukaran.
L berjalan menuju ke kanan dan berhenti di angka 90 sebab 90 > 12.
11 90 23 45 13 43 12 44
     L                       R
                              P

Lalu sehabis itu, tukar posisi 90 dan 12. pindah pivot ke L
11 12 23 45 13 43 90 44
     L                       R
     P
Sekarang, sebab P berada di L, maka R berjalan ke kiri, dan kalau ada angka yang lebih kecil, maka berhenti dan lakukan penukaran.
11 12 23 45 13 43 90 44
     L   R
     P
Ternyata ketika R berada di 23, ternyata 23 masih lebih besar dari 12. Maka dari itu, sebab R sudah sempurna di sebelah kanan L, maka artinya posisi pivot SUDAH TEPAT. Saya beri tanda merah pada pivot yang artinya pivot sudah tidak dapat berubah-rubah.
11 12 23 45 13 43 90 44
     L   R
     P
Sekarang kita lakukan quicksort, pada sebelah kanan dan sebelah kiri pivot.
Sebelah kiri pivot :
11
Karena hanya 1 angka, maka sudah niscaya angka tersebut mempunyai posisi yang tepat jadi saya beri tanda merah.
11 12 23 45 13 43 90 44
kini sebelah kanan pivot yaitu :
23 45 13 43 90 44
Kita lakukan langkah yang sama ibarat pada awal
23 45 13 43 90 44
L                       R
P
Sekarang, R akan berjalan ke kanan dan cari angka yang lebih kecil dari pivot.
23 45 13 43 90 44
L        R
P
Maka R akan berhenti di angka 13 sebab 13 < 23. Lalu lakukan penukaran.
13 45 23 43 90 44
L        R
           P
Sekarang, L akan berjalan ke kanan dan cari angka yang lebih besar dari pivot yaitu 23. 
13 45 23 43 90 44
     L   R
           P
L akan berhenti di angka 45 sebab 45 > 23. Sekarang tukar posisi.
13 23 45 43 90 44
     L   R
     P
Karena R sudah sempurna di sebelah kanan L, maka berhenti ! Pivot sudah mempunyai posisi yang benar. Maka saya akan beri tanda merah.
13 23 45 43 90 44
     L   R
     P
Sekarang lakukan hal yang sama pada sebelah kanan dan sebelah kiri pivot.
Untuk sebelah kiri pivot :
13
Karena 13 hanya 1 angka, maka sudah niscaya 13 mempunyai posisi yang tepat. Jadi, kita lanjutkan untuk sebelah kanan.
13 23 45 43 90 44
sebelah kanan pivot :
45 43 90 44
Caranya sama ibarat diatas.
45 43 90 44
L             R
P
R akan berjalan ke kanan sampai mendapat angka yang lebih kecil dari pivot yaitu 45. 
45 43 90 44
L             R
P
Ternyata 44 sudah lebih kecil, jadi eksklusif tukar
44 43 90 45
L             R
                P
Sekarang L berjalan ke kanan sampai L berada pada angka yang lebih besar dari pivot.
44 43 90 45
           L  R
                P
L berhenti di 90 sebab 90 > 45 (pivot). Maka lakukan penukaran
44 43 45 90
           L  R
           P
Karena R sudah sempurna di sebelah kanan L, maka pivot mempunyai posisi yang tepat sehingga saya beri warna merah. Lalu lakukan quicksort pada sebelah kanan pivot dan sebelah kiri pivot.
44 43 45 90
           L  R
           P
Sebelah kiri pivot :
44 43
L   R
P
Ingat, walaupun R sudah sempurna di sebelah kanan L, namun tetap di cek. apakah R lebih kecil dari pivot ? Ya.. maka tukar. Dibawah ini hasil sehabis penukaran
43 44
L   R
      P
Karena pivot sudah melaksanakan penukaran kini jalankan L ke kanan, ehh ternyata ketika mau berjalan, L sudah sempurna berada di sebelah kiri R. Maka pivot sudah berada pada posisi yang tepat.
43 44
L   R
      P
Lalu lakukan quicksort pada sebelah kanan dan sebelah kiri pivot. Tapi sebab sebelah kanan pivot sudah tidak ada, maka cukup sebelah kiri. Tapi sebab sebelah kiri pivot, cuman ada 1 angka, maka sudah dipastikan angka tersebut mempunyai posisi yang tepat.
43 44
Makara urutannya ibarat ini.
43 44 45 90
Nah, kini kita lakukan quicksort pada sebelah kanan 45. Karena sebelah kanan 45 cuman 1 angka, maka niscaya ya posisinya sudah tepat. Makara posisinya akan ibarat ini.
43 44 45 90
Kita gabungkan dengan urutan yang diatasnya tadi.
13 23 43 44 45 90
Kita gabungkan lagi.
11 12 13 23 43 44 45 90

Selesai ! Maka semua sudah terurut dengan benar.
11 12 13 23 43 44 45 90

Masih belum mengerti ??
Gak apa-apa, Mari kita lihat video ini. Video youtube ini sama persis ibarat cara diatas. 
https://www.youtube.com/watch?v=3OLTJlwyIqQ


Semoga bermanfaat !







Sumber http://komputer67.blogspot.com

Share this post