Memahami Quick Sort Step By Step

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

Sebelumnya, saya beri tahu, bahwa Quicksort memiliki macam-macam variasi. Nah jadi jangan bingung 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, langsung saja kita mulai

Tutorial Quicksort Step By Step

Semisal kita memiliki data seperti ini :

12 90 23 45 13 43 11 44

Pertama, tentukan pivot. Pivot adalah salah satu penanda seperti index. Lalu beri juga tanda bernama 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 jika 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 saat penukaran, pivot ikut bertukar menjadi R.
11 90 23 45 13 43 12 44
L                            R
                              P
Setelah itu, karena P berada di R, maka L berjalan ke kanan, dan jika ada angka yang lebih besar, maka berhenti dan lakukan penukaran.
L berjalan menuju ke kanan dan berhenti di angka 90 karena 90 > 12.
11 90 23 45 13 43 12 44
     L                       R
                              P

Lalu setelah itu, tukar posisi 90 dan 12. pindah pivot ke L
11 12 23 45 13 43 90 44
     L                       R
     P
Sekarang, karena P berada di L, maka R berjalan ke kiri, dan jika ada angka yang lebih kecil, maka berhenti dan lakukan penukaran.
11 12 23 45 13 43 90 44
     L   R
     P
Ternyata saat R berada di 23, ternyata 23 masih lebih besar dari 12. Maka dari itu, karena R sudah tepat di sebelah kanan L, maka artinya posisi pivot SUDAH TEPAT. Saya beri tanda merah pada pivot yang artinya pivot sudah tidak bisa 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 pasti angka tersebut memiliki posisi yang tepat jadi saya beri tanda merah.
11 12 23 45 13 43 90 44
sekarang sebelah kanan pivot yaitu :
23 45 13 43 90 44
Kita lakukan langkah yang sama seperti 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 karena 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 karena 45 > 23. Sekarang tukar posisi.
13 23 45 43 90 44
     L   R
     P
Karena R sudah tepat di sebelah kanan L, maka berhenti ! Pivot sudah memiliki 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 pasti 13 memiliki posisi yang tepat. Jadi, kita lanjutkan untuk sebelah kanan.
13 23 45 43 90 44
sebelah kanan pivot :
45 43 90 44
Caranya sama seperti diatas.
45 43 90 44
L             R
P
R akan berjalan ke kanan hingga mendapatkan angka yang lebih kecil dari pivot yaitu 45. 
45 43 90 44
L             R
P
Ternyata 44 sudah lebih kecil, jadi langsung tukar
44 43 90 45
L             R
                P
Sekarang L berjalan ke kanan hingga L berada pada angka yang lebih besar dari pivot.
44 43 90 45
           L  R
                P
L berhenti di 90 karena 90 > 45 (pivot). Maka lakukan penukaran
44 43 45 90
           L  R
           P
Karena R sudah tepat di sebelah kanan L, maka pivot memiliki 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 tepat di sebelah kanan L, namun tetap di cek. apakah R lebih kecil dari pivot ? Ya.. maka tukar. Dibawah ini hasil setelah penukaran
43 44
L   R
      P
Karena pivot sudah melakukan penukaran sekarang jalankan L ke kanan, ehh ternyata saat mau berjalan, L sudah tepat 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 karena sebelah kanan pivot sudah tidak ada, maka cukup sebelah kiri. Tapi karena sebelah kiri pivot, cuman ada 1 angka, maka sudah dipastikan angka tersebut memiliki posisi yang tepat.
43 44
Jadi urutannya seperti ini.
43 44 45 90
Nah, sekarang kita lakukan quicksort pada sebelah kanan 45. Karena sebelah kanan 45 cuman 1 angka, maka pasti ya posisinya sudah tepat. Jadi posisinya akan seperti 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 seperti cara diatas. 
https://www.youtube.com/watch?v=3OLTJlwyIqQ


Semoga bermanfaat !

Share this post