CONTOH PROGRAM QUICK SORT C++

Posted by : JAUH JAUH HARI Rabu, 07 November 2012

Setelah Postingan saya kemaren mengenai contoh program c++ BUBBLE SORT, SELECTION SORT dan SHELL SORT, Kali ini saya akan menambahkan postingan Saya mengenai salah satu METODE PENGURUTAN DATA atau SORTING dengan 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.

Langsung saja tanpa basa basi saya kasih langsung Source Code'nya :

#include <iostream.h>
#include <conio.h>

void tampilkan_larik(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;

//x=data[awal];
 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_larik(data,n);
 getch();
}