Metoda Pengurutan Quick Sort Dengan Bahasa C

Ada dua metoda pengurutan yang populer, yaitu Bubble Sort dan Quick Sort. Artikel ini membahas metoda 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 menginjak pada pembahasan tentang program pengurutan dengan metoda Quick Sort, terlebih dahulu akan diberikan ilustrasi terlebih dahulu.

Gambar 1

Katakanlah Anda memiliki 7 buah angka yang harus diurutkan, yaitu 5, 1, 3, 10, 8, 6, dan 7. Lihat ilustrasi pada gambar 1 di atas. 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 :

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.