QUICK
SORT
AHMAD
FAJAR SUSILO
2115R1067
PENGERTIAN QUICK SORT
Algoritma quick sort diperkenalkan pertama kali oleh C.A.R.
Hoare pada tahun 1960, dan dimuat sebagai artikel di “Computer
Journal 5” pada April 1962. Quick
sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda
divide-and-conqueror. Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat
cepat.
Algoritma quick sort mengurutkan
dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara
rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk
beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih
cepat dibandingkan algoritma quick sort.
Quick Sort merupakan suatu algoritma pengurutan data yang
menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini
disebut juga dengan nama partition exchange sort. Untuk memulai irterasi
pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian
elemen-elemen data akan diurutkan diatur sedemikian rupa
Strategi divide-and-conqueror digunakan di dalam
quicksort.
Di bawah ini akan dijelaskan langkah-langkahnya:
Di bawah ini akan dijelaskan langkah-langkahnya:
Pilih nilai pivot Kita ambil nilai
di tengah-tengah elemen sebagai sebagai nilaidari pivot tetapi bisa
nilai mana saja.
Partisi Atur ulang semua
elemen sedemikian rupa, lalu semua elemen yang lebihrendah daripada pivot dipindahkan ke sebelah
kiri dari array/list dan semuaelemen yang lebih besar dari pivot dipindahkan ke sebelah
kanan dari array/list. Nilai yang sama dengan pivot
dapat diletakkan di mana saja dari array. Ingat,mungkin
array/list akan dibagi dalam bagian yang tidak sama.
Urutkan semua bagian (kiri/kanan) Aplikasikan
algoritma quicksort secararekursif pada bagian sebelah kiri dan kanan.
Algoritma Partisi secara detail
Ada dua indeks i dan j dan pada awal algoritma partisi i
menunjuk ke elemen pertama dalam array dan poin j yang terakhir. Kemudian
algoritma menggerakkan i ke depan, sampai elemen dengan nilai yang lebih besar
atau sama dengan pivot ditemukan. Indeks j bergerak mundur, sampai elemen
dengan nilai yang lebih rendah atau sama dengan pivot ditemukan.
Jika i ≤ j maka mereka bertukar dan saya
langkah ke posisi berikutnya (i + 1), langkah-langkah j
dengan yang sebelumnya (j - 1). Algoritma berhenti, ketika saya menjadi lebih
besar dari j. Setelah partisi, semua nilai sebelum elemen ke-i kurang atau sama
dengan pivot dan semua nilai setelah elemen ke-j lebih besar atau sama dengan
pivot.
KELEBIHAN
Algoritma Quicksort memiliki kompleksitas O(n log n) dimana
pada prakteknya lebih cepat dari algoritma pengurutan lainnya.
KEKURANGAN
Pada kemungkinan terburuknya, algoritma Quicksort ini dapat
memiliki kompleksitas O(n2). Meskipun ini sangat langka terjadi
Image Exampel Quick Sort
SUMBER
:
http://catatan-ati.blogspot.co.id/2015/08/pengertian-quick-sort-dan-implementasi.html#sthash.X4k9S9jC.dpuf
SEKIAN
DAN
TERIMA KASIH
DAN
TERIMA KASIH
Comments
Post a Comment