Metode Pemograman Algoritma Quick Sort

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 <-- br="" p="" partisi="" 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 <-- br="" l="" p="">i <-- br="" p="">j <-- br="" r="">ULANG SAMPAI BENAR
ULANG SELAMA L[j] > x
j <-- br="" i="" j="">AKHIR – ULANG
ULANG SELAMA L[I] < x
i<--i br="">AKHIR-ULANG
JIKA i//Tukarkan L[i] dengan L[j]
tmp=L[i]
L[i] <-- br="" j="" l="">L[j]<--tmp br="">SEBALIKNYA
NILAI – BALIK j
AKHIR-JIKA
AKHIR-ULANG
AKHIR-SUBRUTIN

Pertama-tama x <-- adalah="" bagian="" bergerak="" bergeser="" berupa="" dalam="" dan="" daripada="" dengan="" digeser="" dilakukan="" dipakai="" disebut="" dua="" elemen="" hal="" i="" ini="" j.="" j="" kanan="" kecil="" kiri="" kondisi="" l="" larik="" lebih="" membagi="" memenuhui="" menggunakan="" menjadi="" naik="" nilai="" p..r="" pemartisian="" penunjuk="" petunjuk="" pivot.="" pivot="" q="" sampai="" secara="" sedangkan="" sehingga="" selalu="" semua="" terus-menerus="" turun.="" turun="" untuk="" variabel="" varibel="" yang="">= 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
#include

void tampilkan_larik(int data[], int n)
{
int i;
for (i=0;icout<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]i=i+1;

if (i{
//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{
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: "<for(int ctr=0; ctr<9 br="" ctr="">{
cout<}
quick_sort(data,0,jum_data-1);

//hasil pengurutan
cout<cout<cout<<"hasil pengurutan:\n";
tampilkan_larik(data,jum_data);
getch();
}

Sumber : http://allaboutalgoritma.blogspot.com/2009/06/metode-quick-sort.html