Metode Quick Sort Di C++

Semua Tulisan Yang Terposting Di Website HMPS TI Univ. Kanjuruhan Malang adalah Sepenuhnya Hak Cipta dari HMPS TI. Untuk Saran silahkan layangkan pesan anda ke hmpstikanjuruhan@gmail.com. Terimakasih, Salam YES.

Algoritma Quick Sort ditemukan oleh C.A.R Hoare. Quick sort, sesuai dengan namanya, diklaim sebagai algoritma pengurutan yang lebih cepat dari algoritma pengurutan lainnya.

Namun, algoritma ini, menurut saya sendiri pun, dinilai cukup sulit difahami dibanding dengan yang lainnya, karena untuk menguasai algoritma ini, diperlukan pengetahuan mengenai algoritma rekursif dan pola divide-and-concuer. Apaan tuh ? Dibawah ini saya ulaskan sedikit (sangat sedikit ) mengenai kedua pola tersebut.

Divide

Memilah kelompok data menjadi dua sub-kelompok data.

Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif.

Rekursif

Metode dimana isi dari sebuah fungsi mengandung pemanggilan fungsi itu sendiri.

Untuk lebih jelasnya bisa dilihat pada syntax di bawah ini :

#include<iostream.h>
#include<conio.h>
#include<iomanip.h>
#define n 8

class quick{
   static int data[n];
 public:
   void tukar(int a,int b);
   void QuickSort(int l, int r);
   void tampil();
};
void main(){
  quick x;
  cout<<endl<<"Data sebelum diurutkan:"<<endl;
  x.tampil();
  x.QuickSort(0,n-1);
  cout<<endl<<"Data setelah diurutkan:"<<endl;
  x.tampil();
  getch();
}

int quick::data[n]={7,4,98,9,2,1,17,20};

void quick::tukar(int a,int b){
  int t;
  t=data[b];
  data [b]=data[a];
  data[a]=t;
}
void quick::QuickSort(int l,int r){
  int i,j,mid;
  i=l;  j=r;
  mid=data[(l+r)/2];
  do{
    while(data[i]<mid)i++;
         while(data[j]>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 quick::tampil(){
 for(int j=0;j<n;j++) cout<<data[j]<<setw(3);
       cout<<endl;
}