Quick Sort

Hai hai kembali lagi dengan saya. Untuk kali ini saya akan berbagi ilmu tentang Quick sort.

Oke, tanpa banyak basa basi. Langsung saja simak penjelasannya dibawah ini.


Apa sih quick sort? Quick sort sendiri dikembangkan oleh Tony Hoare pada tahun 1960 dan mulai diperkenalkan dua tahun setelahnya yaitu pada tahun 1962.

Kok bisa disebut quick sih? Apa beneran cepat atau cuman namanya saja yang cepat? Quick sort memanglah yang tercepat untuk soal menyusun data dibandingkan dengan metode sorting lainnya. Dan metode ini pun memiliki kompleksivitas dan pemprosesanya pun dilakukan secara rekursif atau berulang-ulang.

Langsung saja pada contoh dan ilustrasi dibawah ini.

Kita memiliki data seperti pada gambar diatas. Nah langkah berikutnya adalah menentukan pivot atau elemen awal, tengah ataupun akhir dalam suatu array. Cara menentukannya adalah dengan cara, pivot = (i + j) / 2. pivot = (1 + 8)/2 = 4.5. Karena hasilnya mengandung koma lebih dari sama dengan 5, maka kita dapat memilih angka yang akan diambil. Angka 4 atau angka 5 (hasil pembulatan dari 4.5). Untuk kali ini kita akan mengambil angka 4 sebagai pivotnya.

Langkah selanjutnya adalah mengecek i dan j. Apakah i > pivot, jika iya maka i akan berhenti, jika tidak maka i + 1. Begitu pula dengan j, hanya saja jika j tidak lebih kecil dari pivot maka j - 1. Untuk tau kapan penukarannya dilakukan, penukaran elemen dilakukan ketika i sudah tidak berpindah ke elemen berikutnya begitu juga dengan j hanya saja j berpindah ke elemen sebelumnya (karena j - 1). Oke langsung saja lakukan penukaran. Dan di bawah ini adalah hasil pertukarannya

Gambar diatas adalah hasil dari penukarannya. Eits, ini belum selesai karena i > j maka pembagian partisi pun sudah terbagi menjadi dua partisi.

Kita bisa mulai mencarinya di partisi sebelah kiri. Lakukan langkah yang sama untuk setiap partisinya.

Dan hasil akhirnya adalah sebagai berikut :

Nah, itu adalah hasil akhir dari proses quick sort. Cepat kan prosesnya hanya saja algoritmanya yang lebih kompleks dibandingkan dengan sorting yang lain. Gak percaya kalau quick sort algoritmanya lebih kompleks dari sorting yang lainnya? Coba lihat contoh program quick sort dalam bahasa c++ dibawah ini.


Pusingkan?

Terima kasih atas waktunya. Jika ada pertanyaan bisa langsung komentar saja di post ini!!!

Sumber :
https://id.wikipedia.org/wiki/Quicksort
https://rizarulham.wordpress.com/2009/10/07/algoritma-quick-sort/
http://dtugasalgoritma.blogspot.co.id/2010/12/quick-sort-algoritma.html
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/quickSort.htm