Beranda / Unlabelled / Pengertian Quick Sort dan implementasi

Pengertian Quick Sort dan implementasi

Posted by Catatan-ati Saturday, 29 August 2015 4 komentar

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 iniakan 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

Video Exampel Quick Sort

TERIMA KASIH ATAS KUNJUNGANNYA

Judul artikel :Pengertian Quick Sort dan implementasi
Ditulis oleh :Catatan-ati
Rating Blog :5 dari 5

Semoga artikel ini bermanfaat bagi saudara. Jika ingin mengutip,baik itu sebagian atau keseluruhan dari isi artikel ini harap menyertakan link dofollow ke: http://catatan-ati.blogspot.com/2015/08/pengertian-quick-sort-dan-implementasi.html.Terima kasih sudah singgah membaca artikel ini.