Saturday, August 1, 2015
Pada pembahasan
sebelumnya Anda telah mengetahui bahwa setidaknya ada dua metoda pengurutan
yang populer, yaitu Bubble Sort dan Quick Sort. Sengaja metoda Bubble Sort
dipilih untuk dibahas terlebih dahulu karena logikanya mudah untuk diikuti.
Nah, sekarang
kita menginjak pada metoda pengurutan yang kedua yaitu Quick Sort. Metoda ini
mungkin memang tidak semudah Bubble Sort, akan tetapi unggul dalam segi
kecepatan, terutama apabila ada banyak data yang harus diurutkan.
Sebelum kita
menginjak pada pembahasan tentang program pengurutan dengan metoda Quick Sort, terlebih
dahulu akan diberikan ilustrasi terlebih dahulu.
Katakanlah Anda
memiliki 7 buah angka yang harus diurutkan, yaitu 5, 1, 3, 10, 8, 6, dan 7.
Lihat ilustrasi pada gambar 1.
 |
| gambar 1 |
Dengan menggunakan metoda Quick Sort, langkah
pertama yang harus diambil adalah menentukan elemen pivot. Elemen pivot adalah
suatu data yang dipilih untuk menjadi dasar acuan dalam pengurutan data. Elemen
ini boleh diambil sembarang, salah satu dari ketujuh data tersebut. Dalam
contoh ini akan diambil angka 7 sebagai elemen pivot. Lihat ilustrasi pada
gambar 2.
 |
| gambar 2 |
Langkah
berikutnya adalah melakukan pembandingan seluruh elemen yang ada dengan elemen
pivot tersebut. Sebagai hasil dari pembandingan tersebut, bilangan yang lebih
kecil daripada elemen pivot akan diletakkan di sebelah kiri elemen pivot dan
bilangan yang lebih besar daripada elemen pivot diletakkan di sebelah kanan
elemen pivot. (Kasus ini berlaku untuk pengurutan dari bilangan terkecil ke
bilangan terbesar atau ascending).
Proses
pembandingan ini dapat dilakukan dari dua arah, yaitu dari arah kiri dan dari
arah kanan. Nantinya dalam program, gerakan dari arah kiri akan dinotasikan
dengan huruf i dan gerakan dari arah kanan akan dinotasikan dengan huruf j.
Lihat ilustrasi pada gambar 3.
 |
| gambar 3 |
Apabila elemen i memiliki nilai lebih besar
daripada elemen pivot dan elemen j memiliki nilai lebih kecil daripada elemen
pivot, maka kedua elemen ini ditukar letaknya. Proses ini akan dilakukan terus
hingga kedua arah gerakan bertemu di suatu titik tertentu. Lihat ilustrasi pada
gambar 4. (Perhatikan bahwa letak urutan angka telah berubah).
 |
| gambar 4 |
Selanjutnya
letak elemen pivot ditukar dengan letak titik temu tersebut. Lihat ilustrasi
pada gambar 5.
 |
| gambar 5 |
Hasil akhir proses ini terlihat pada gambar 6.
 |
| gambar 6 |
Perhatikan
baik-baik gambar 6 tersebut. Pada keadaan tersebut, seluruh bilangan yang
terletak di sebelah kiri elemen pivot bernilai lebih kecil daripada elemen
pivot dan seluruh bilangan yang terletak di sebelah kanan elemen pivot bernilai
lebih besar daripada elemen pivot. Jumlah elemen yang terletak di sebelah kiri
dan kanan tidak harus sama.
Sekalipun
sekarang seluruh bilangan yang terletak di sebelah kiri elemen pivot bernilai
lebih kecil daripada elemen pivot dan seluruh bilangan yang terletak di sebelah
kanan elemen pivot bernilai lebih besar daripada elemen pivot, namun
bilangan-bilangan tersebut masih belum berurutan. Jadi proses Quick Sort harus
dilakukan lagi untuk bilangan yang terletak di sebelah kiri elemen pivot dan di
sebelah kanan elemen pivot.
Proses ini akan
terus berlangsung hingga seluruh bilangan akan terurut.
Nah, berdasarkan
ilustrasi di atas, sekarang akan kita bangun program yang akan melakukan proses
pengurutan dengan metoda Quick Sort. Program tersebut diberikan pada listing 1.
|
Listing 1. Program pengurutan metoda Quick Sort
#include <stdio.h>
#define N 20
int quick(int bawah, int atas);
int i, j, A[N];
main()
{
int jml;
clrscr();
printf("MENGURUTKAN DATA DENGAN QUICK SORT \n\n");
printf("Masukkan jumlah bilangan (maks 20) : ");
scanf("%d",&jml);
// input data
for (i=0;i<jml;i++)
{
printf("Bilangan
ke %d : ",i+1);
scanf("%d",&A[i]);
}
// pengurutan data
quick(0,jml-1);
// menampilkan hasil
printf("Data yang telah terurut : \n");
for (i=0;i<jml;i++)
{
printf("%d\n",A[i]);
}
}
// fungsi quick
int quick(int bawah, int atas)
{
int pivot, temp;
// pengulangan dilakukan
// selama bawah < atas
if (bawah<atas)
{
i = bawah;
j = atas;
pivot = A[j];
do
{
while
(i<j && A[i]<=pivot)
{
i++;
}
while
(j>i && A[j]>=pivot)
{
j--;
}
if
(i<j)
{
temp
= A[i];
A[i]
= A[j];
A[j]
= temp;
}
}
while
(i<j);
temp = A[j];
A[j] =
A[atas];
A[atas] =
temp;
if
(j-bawah<atas-i)
{
quick(bawah,j-1);
quick(i+1,atas);
}
else
{
quick(i+1,atas);
quick(bawah,j-1);
}
}
}
|
Salah satu
kemungkinan hasil apabila program tersebut dijalankan adalah sebagai berikut:
MENGURUTKAN DATA DENGAN QUICK SORT
Masukkan jumlah bilangan (maks 20) : 7
Bilangan ke 1 : 5
Bilangan ke 2 : 1
Bilangan ke 3 : 3
Bilangan ke 4 : 10
Bilangan ke 5 : 8
Bilangan ke 6 : 6
Bilangan ke 7 : 7
Data yang telah terurut :
1
3
5
6
7
8
10
Bandingkan
dengan gambar 7.
 |
| gambar 7 |
Perhatikan
dengan seksama program tersebut. Anda akan melihat bahwa di dalam fungsi
quick() dipanggil lagi fungsi quick() itu sendiri. Tentunya Anda masih ingat
bukan bahwa hal tersebut merupakan fungsi rekursif.
Sebagai latihan,
Anda bisa membuat program yang sama namun untuk pengurutan descending atau
menurun. Selamat mencoba.
