Quick Sort

Algoritma Quick Sort

Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.

2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.

3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT. Berikut pseudocode dari algoritma quick sort :

Procedure QuickSort (input/output a : array [1..n] of integer, input i , j : integer )

{mengurutkan tabel a[i..j] dengan algoritma quick sort. Masukkan: Tabel a[i..j] yang sudah

terdefinisi elemen-elemennya. Keluaran: Tabel a[i..j] yang terurut menaik.}

Deklarasi :

k : integer;

Algoritma :

if (i<j) then

Partisi(a,i,j,k) { Ukuran (a) > 1}

QuickSort(a,i,k)

QuickSort(a,k+1, j)

Endif

Procedure Partisi (input/output: a : array[1..n] of integer, input i , j : integer, output q : integer)

{Membagi tabel a[i..j] menjadi subtabel a[i..q] dan a[q+1..j]. Keluaran upatabel a[i..q] dan subtabel a[q+1..j]. Sedemikian sehingga elemen tabel a[i..q] lebih kecil dari elemen tabel a[q+1..j]}

Deklarasi :

Pivot, temp : integer

Algoritma :

Pivot <- A[(i+j) div 2] { pivot = elemen tengah }

p <- i

q <- j

repeat

while a[p] < pivot do

p <- p + 1

endwhile

{ Ap >= pivot }

while a[q] > pivot do

q <- q – 1

endwhile

{ Aq >= pivot }

if (p _ q) then

{ pertukarkan a[p] dengan a[q]}

temp <- a[p]

a[p] <- a[q]

a[q] <- temp

{ tentukan awal pemindaian berikutnya}

p <- p+ 1

q <- q – 1

endif

until p > q

Kompleksitas Algoritma Quick Sort

Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai pivot. Dalam menghitung kompleksitas ini, perlu dilihat pula perhitungan recurrence, karena terdapat fungsi rekursif untuk penyelesaian sub-masalah.

Terdapat 3 jenis kompleksitas waktu dari quicksort:

1. Kasus terburuk (worst case), yaitu terjadi bila terbentuk partisi dengan komposisi sub-masalah antara n – 1 elemen dan 0 elemen. Dengan demikian pemanggilan fungsi secara rekursif dengan array berukuran 0 akan langsung kembali, T(0) = Θ(1), sehingga berlaku: T(n) = T(n – 1) + cn = O(n²).
2. Kasus terbaik (best case), yaitu terjadi bila terbentuk partisi dengan dengan komposisi seimbang, dengan ukuran masing-masing tidak lebih dari n/2. Sehingga didapat: T(n) = 2T(n/2) + cn = na + cn log n = O(n log n).
3. Kasus rata-rata (average case), yaitu terjadi dari perimbangan pivot antara terbaik dan terburuk, yang dalam prakteknya lebih mendekati kasus terbaik ketimbang terburuk. Sehingga didapat: T_avg(n) = O(n log n).

Kelebihan dan Kelemahan Algoritma Quick Sort

Beberapa hal yang membuat quick sort unggul:

• Secara umum memiliki kompleksitas O(n log n).
• Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman dan arsitektur mesin secara efisien.
• Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.
• Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
• Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).

Namun terdapat pula kelemahan quick sort:

• Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
• Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n²).
• Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
• Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

Implementasi Algoritma Quick Sort

Berikut adalah implementasi dari quick sort dalam bahasa C. Implementasinya terbagi menjadi dua prosedur, yaitu prosedur partisi dan prosedur quicksort.

void quicksort(int x[], int first, int last) {

int pivIndex = 0;

if(first < last) {

pivIndex = partition(x,first, last);

quicksort(x,first,(pivIndex-1));

quicksort(x,(pivIndex+1),last);

}

}

int partition(int y[], int f, int l) {

int up,down,temp;

int piv = y[f];

up = f;

down = l;

goto partLS;

do {

temp = y[up];

y[up] = y[down];

y[down] = temp;

partLS:

while (y[up] <= piv && up < l) {

up++;

}

while (y[down] > piv  && down > f ) {

down–;

}

} while (down > up);

y[f] = y[down];

y[down] = piv;

return down;

}