Quick sort

Posted: November 11, 2010 in Algoritma & Struktur Data

Algoritma quick sort diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960.Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metoda divide-and-conqueror. Disebut Quick Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat.
Quick sort disebut juga dengan partition exchange sort, karena konsepnya membuat partisi-partisi, dan sort dilakukan per partisi.
Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk.

Berikut beberapa cara pemilihan pivot :

1. Pivot adalah elemen pertama, elemen terakhir, atau elemen tengah tabel. Cara ini hanya bagus jika elemen tabel tersusun secara acak, tetapi tidak bagus jika elemen tabel semula sudah terurut. Misalnya, jika elemen tabel semula menurun, maka semua elemen tabel akan terkumpul di upatabel kanan.

2. Pivot dipilih secara acak dari salah satu elemen tabel. Cara ini baik, tetapi mahal, sebab memerlukan biaya (cost) untuk pembangkitan prosedur acak. Lagi pula, itu tidak mengurangi kompleksitas waktu algoritma.

3. Pivot adalah elemen median tabel. Cara ini paling bagus, karena hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang (masing masing ≈ n/2 elemen). Cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri.

Algoritma Quick Sort terdiri dari dua prosedur, yaitu prosedur PARTISI dan prosedur QUICKSORT.

contoh quicksort :

#include
#include
#include
int data[100];
int n;
void tukar(int a,int b)
{
int t;
t=data[b];
data[b]=data[a];
data[a]=t;
}
void input()
{
cout<>n;
for(int i=0;i<n;i++)
{
cout<<"Masukan data ke-"<<(i+1)<>data[i];
}
}
void quicksort(int L,int R)
{
int i,j,mid;
i=L;
j=R;
mid=data[(L+R)/2];
do
{
while(data[i]mid)
{
j–;
}
if(i<=j)
{
tukar(i,j);
i++;
j–;
}
}
while(i<j);
if(L<j)
quicksort(L,j);
if(i<R)
quicksort(i,R);
}
void tampil()
{
for(int j=0;j<n;j++)
cout<<data[j]<<setw(3);
cout<<endl;

}
void main()
{
input();
cout<<endl<<"Data sebelum di urutkan :"<<endl;tampil();
quicksort(0,n-1);
cout<<endl<<"Data sesudah diurutkan :"<<endl;tampil();
getch();
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s