Algoritma quick sort diperkenalkan pertama kali oleh C.A.R.
Hoare pada tahun1960, dan dimuat sebagai artikel di “Computer Journal
5” pada April 1962. Quick sort adalah algoritma sorting yang
berdasarkan pembandingan dengan metoda divide-and-conqueror. Disebut Quick
Sort, karena Algoritma quick sort mengurutkan dengan sangat cepat.
Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa
Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sangat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa
Strategi divide-and-conqueror digunakan di
dalam quicksort.
Di bawah iniakan dijelaskan langkah-langkahnya :
Di bawah iniakan dijelaskan langkah-langkahnya :
1. Pilih nilai pivot Kita ambil nilai di
tengah-tengah elemen sebagai sebagai nilaidari pivot tetapi
bisa nilai mana saja.
2. Partisi Atur ulang semua elemen sedemikian
rupa, lalu semua elemen yang lebihrendah daripada pivot dipindahkan
ke sebelah kiri dari array/list dan semuaelemen yang lebih besar dari pivot dipindahkan
ke sebelah kanan dari
array/list. Nilai yang sama dengan pivot dapat
diletakkan di mana saja dari array. Ingat,mungkin array/list akan dibagi
dalam bagian yang tidak sama.
3. Urutkan semua bagian (kiri/kanan) Aplikasikan
algoritma quicksort secararekursif pada bagian sebelah kiri dan kanan.
#include <iostream>
#include <conio.h>
using namespace std;
void tampilkan_data(int data[], int n)
{
int i;
for
(i=1;i<=n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
int partisi (int data[], int awal, int akhir)
{
int
x,i,j,simpan;
//www.nutekno.com
i=awal;
j=akhir;
while(1)
{
while(data[i]<data[awal])
i=i+1;
while(data[j]>data[awal])
j=j-1;
if (i<j)
{
//tukarkan
data
simpan=data[i];
data[i]=data[j];
data[j]=simpan;
}
else
return j;
}
}
void quick_sort(int data[], int awal, int akhir)
{
int q;
if(awal<akhir)
{
q=partisi(data,awal,akhir);
quick_sort(data,awal,q);
quick_sort(data, q+1,akhir);
}
}
int main()
{
int
i,j,n,data[100];
cout<<"masukkan banyak data= ";cin>>n;
for(i=1;i<=n;i++)
{
cout<<"data ke-"<<i<<" =
";cin>>data[i];
}
cout<<"Data sebelum diurut:
"<<endl;
for(j=1;j<=n;j++)
{
cout<<data[j]<<"
";
}
quick_sort(data,1,n);
//hasil
pengurutan
cout<<endl;
cout<<endl;
cout<<"hasil pengurutan:\n";
tampilkan_data(data,n);
getch();
}
hasil running :
Sumber :
0 Komentar