Quick Sort adalah metode membagi list yang besar menjadi dua buah partisi yang lebih kecil kemudian menyortir partisi-partisi tersebut secara rekursif (fungsi yang didalam implementasinya memanggil dirinya sendiri). Pertama-tama memilih elemen tengah dalam array untuk dijadikan pembanding (pivot). Partisi-partisi tersebut yang akan diurutkan dan dikelompokkan menjadi elemen-elemen dengan kelompok nilai kecil dan kelompok nilai besar. Kelompok tersebut diperoleh dari elemen-elemen antara index awal sampai pivot dan elemen-elemen antara pivot sampai index akhir. Proses tersebut akan diulang secara rekursif sehingga semakin lama ukuran sub array atas dan sub array bawah semakin kecil dan akhirnya seluruh elemen terurut dengan sempurna.
Script:
#include<iostream>
using namespace std;
void tukar(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void quicksort(int val[], int left, int right, char o)
{
int x = left, y = right;
int pivot = val[(left + right) / 2];
if(o == 'A')
{
do
{
while (val[x] < pivot)
x++;
while (val[y] > pivot)
y--;
if (x <= y)
{
tukar(val[x], val[y]);
x++;
y--;
};
}
while (x < y);
}
else if(o == 'D')
{
do
{
while (val[x] > pivot)
x++;
while (val[y] < pivot)
y--;
if (x <= y)
{
tukar(val[x], val[y]);
x++;
y--;
};
}
while (x < y);
}
if (left < y)
quicksort(val, left, y, o);
if (x < right)
quicksort(val, x, right, o);
}
int main()
{
char urut;
int nilai[100];
int z, jumlah;
cout<<"Jumlah Data : ";
cin>>jumlah;
cout<<"Urut [A/D] : ";
cin>>urut;
cout<<"--------------------------------\n";
for(z = 0; z < jumlah; z++)
{
cout<<"Nilai ke-"<<1 + z<<" : ";
cin>>nilai[z];
}
quicksort(nilai, 0, jumlah - 1, urut);
cout<<"--------------------------------\n";
cout<<" HASIL SORTIR \n";
cout<<"--------------------------------\n";
for(z = 0; z < jumlah; z++)
{
cout<<nilai[z]<<" ";
}
return 0;
}
No comments:
Post a Comment