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 <-- 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();

}

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