Quicksort

Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif.

Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

ALGORITMA

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

if (rightIdx > leftIdx) {

pivotIdx = partition(array, leftIdx, rightIdx);

quickSort(array, leftIdx, pivotIdx-1);

quickSort(array, pivotIdx+1, rightIdx);

}

}

Contoh :

Rangkaian data:

Pilih sebuah elemen yang akan menjadi elemen pivot. Contoh pivot = 3

Inisialisasi elemen kiri sebagai elemen kedua dan elemen kanan sebagai elemen akhir.

Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen pivot tersebut dan geser elemen kanan ke arah kiri sampai ditemukan nilai dari elemen yang tidak lebih besar dari elemen tersebut.

Tukarkan antara elemen kiri dan kanan

Geserkan lagi elemen kiri dan kanan.

Tukarkan antar elemen kembali.

Geserkan kembali elemen kiri dan kanan.

Terlihat bahwa titik kanan dan kiri telah digeser sehingga mendapatkan nilai elemenkanan < elemen kiri. Dalam hal ini tukarkan elemen pivot dengan elemen kanan.

Kemudian urutkan elemen sub-rangkaian pada setiap sisi dari elemen pivot.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: