Metode Pengurutan Quicksort

Nama : Maulana Aji Pratama
NPM : 56414461
Kelas : 1IA17
Mata Kuliah : Algoritma & Pemrograman A
Dosen : Kunto Bayu A, ST.

Metode Pengurutan Quicksort

"Sorting quicksort anim" by Wikipedia:en:User:RolandH - originally upload on the English Wikipedia. Licensed under CC BY-SA 3.0 via Wikimedia Commons.

Membandingkan suatu elemen (pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen-elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanan. Sehingga dengan demikian telah terbentuk dua sublist kiri dan sublist kanan dari pivot.

Secara singkat, prosedur dapat dijabarkan sebagai berikut:
1.    Pilih satu data sebarang sebagai data pivot, misalkan x.
2.    Baca data dari ujung kanan ke kiri sampai ditemukan data a[i] sehingga a[i] < x (partisi kiri).
3.    Baca data dari ujung kiri ke kanan sampai ditemukan data a[j] sehingga a[j] > x (partisi kanan).
4.    Tukar kedua data a[i] dan a[j].
5.    Ulangi proses di atas sampai seluruh data terbagi dua bagian kiri yang lebih kecil dari x dan kanan yang lebih besar dari x.

Prinsip dasar dari quicksort adalah melakukan partisi dari data, dalam dua bagian. Kemudian secara rekursif melakukan sorting pada kedua bagian data tersebut. Algoritma quicksort adalah sebagai berikut:
1.    Tentukan unsur pivot yang diperlukan (gunakan data tengah sebagai unsur pivot).
2.    Partisi data dalam dua bagian yang dipisahkan oleh unsur pivot.
3.    Secara rekursif sort terhadap kedua bagian data diatas dengan dengan metode partisi (ulangi langkah 1 dan 2 untuk data sebelah kiri dan kanan).

Contoh:
Diberikan data berikut :

44 55 12 42 94 6 18 67

unsur pivot yang digunakan adalah 42 yang merupakan data tengah pada deretan data tersebut. Dengan menggunakan prosedur partisi urutan data menjadi:

18 6 12 42 94 55 44 67

Setelah itu data 18, 6, 12 lebih kecil dari 42 dan data 94, 55, 44, 67 lebih besar dari 42.
Data kiri:    18    6    12
Data kanan:    42    94    55    44    67

Proses partisi untuk data kiri.
Untuk data kiri dilakukan partisi lagi, unsur pivotnya adalah 6.
Sub data kiri:    tidak ada karena tidak ada data yang lebih kecil dari 6
Sub data kanan:    6    12    18

Untuk sub data kiri dilakukan partisi lagi, unsur pivotnya adalah 12.
Sub data kiri:   6
Sub data kanan:   12   18
Proses rekursif data untuk Data kiri selesai.

Proses partisi untuk data kanan.
Data di sebelah kanan dipartisi lagi, dengan unsur pivotnya adalah 55.
Sub data kiri:    42    44
Sub data kanan:    55    94    67

Untuk sub data kanan dilakukan partisi lagi, dengan unsur pivotnya adalah 94.
Sub data kiri:    55    67
Sub data kanan:    94
Proses rekursif untuk Data kanan selesai.

Data setelah pengurutan menjadi:

6 12 18 42 44 55 67 94

Jumlah partisi yang dilakukan untuk metode pengurutan quicksort adalah n^2 dimana n merupakan jumlah data. Jika unsur partisinya merupakan median dari data, maka jumlah partisisnya menjadi n log n (dikutip dari buku A Book on C ).

Sumber:
https://irwananwar.files.wordpress.com/2012/05/quicksort.pdf