Quick Sort adalah metode pengurutan data yang dikemukan pertama kali oleh C.AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-pecah” dengan mekanisme seperti berikut : Larik L[p..r] (dengan indeks terkecil adalah p dan indeks terbesar yaitu r) disusun ulang (dipartisi) menjadi dua buah larik A[p..q] dan A[q+1..r] sehingga setiap elemen dalam A[q+1..r]. Selanjutnya kedua larik tersebut diurutkan secara rekursif. Dengan sendirinya kombinasi kedua larik tersebut membentuk larik dengan data yang telah urut.
Implementasi quick sort dapat dilihat di bawah ini.
Algoritma :
SUBRUTIN quick_sort (L,p,r]
JIKA p <-- partisi (L,p,r)
Quick_sort (L,p,r)
Quick_sort (L,q+1,r)
AKHIR – JIKA
AKHIR – SUBRUTIN
Untuk mengurutkan isi keseluruhan larik L, diperlukan pemanggilan seperti berikut :
Quick_sort (L,0,jumlah_elemen(L)-1)
Subrutin partisi sendiri seperti berikut :
SUBRUTIN partisi (L,p,r)
x <-- L[p]
i <-- p
j <-- r
ULANG SAMPAI BENAR
ULANG SELAMA L[j] > x
j <-- j – i
AKHIR – ULANG
ULANG SELAMA L[I] < x
i<--i +1
AKHIR-ULANG
JIKA i<j MAKA
//Tukarkan L[i] dengan L[j]
tmp=L[i]
L[i] <-- L[j]
L[j]<--tmp
SEBALIKNYA
NILAI – BALIK j
AKHIR-JIKA
AKHIR-ULANG
AKHIR-SUBRUTIN
Pertama-tama x <-- L[q] dipakai untuk membagi larik L[p..r] menjadi dua bagian (disebut pemartisian) dengan kondisi semua elemen bagian kiri selalu lebih kecil daripada nilai elemen pivot dan nilai semua elemen bagian kanan selalu lebih kecil daripada nilai elemen pivot. Pemartisian dilakukan dengan menggunakan varibel i dan j. Dalam hal ini i berupa petunjuk yang bergerak naik, sedangkan j adalah penunjuk bergerak turun. Variabel j bergeser turun secara terus-menerus sehingga L[j]<= elemen pivot, sedangkan i digeser naik secara terus-menerus sampai memenuhui kondisi L[j] >= elemen pivot. Proses pengulangan dilakukan sampai nilai i >= j. Pada keadaan seperti ini nilai balik subrutin partisi berupa j.
Ilustrasi pemartisian larik
Implementasi ke dalam bahasa c++
#include <iostream.h>
#include <conio.h>
void tampilkan_larik(int data[], int n)
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
int partisi (int data[], int p, int r)
{
int x,i,j,tmp;
x=data[p];
i=p;
j=r;
while(1)
{
while(data[j]>x)
j=j-1;
while(data[i]<x)
i=i+1;
if (i<j)
{
//tukarkan data
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
else
return j;
}
}
void quick_sort(int data[], int p, int r)
{
int q;
if(p<r)
{
q=partisi(data,p,r);
quick_sort(data,p,q);
quick_sort(data, q+1,r);
}
}
int main()
{
const jum_data=9;
int i;
int data[]={25,57,48,37,12,92,80,33,1};
cout<<"Data sebelum diurut: "<<endl;
for(int ctr=0; ctr<9; ctr++)
{
cout<<data[ctr]<<" ";
}
quick_sort(data,0,jum_data-1);
//hasil pengurutan
cout<<endl;
cout<<endl;
cout<<"hasil pengurutan:\n";
tampilkan_larik(data,jum_data);
getch();
}Labels: Cplusplus
