Anda Pengunjung Ke :

Jumat, 07 Oktober 2011

Program quick sort

Metode sorting dengan quicksort cukup sulit dipahami, namun metode ini
merupakan metode sorting tercepat yang ada saat ini. Metode ini menggunakan
paradigma devide-conquer, sehingga dalam prosesnya, metode ini membagi array
menjadi 2 bagian untuk selanjutnya diproses kembali secara rekursif dengan
memanggil dirinya sendiri (prosedur quicksort itu sendiri).
Di dalam metode ini dikenal beberapa istilah, yakni :
1. Pivot
Sembarang elemen array yang digunakan sebagai batas. Pivot ini dapat dipilih
secara random, atau dengan memilih elemen yang berada di tengah array.
2. Partisi
Hasil pembagian array menjadi 2 sub-array melalui proses pemartisian.
Berikut ini ilustrasi algoritma quicksort.



#include <iostream.h>
#include <conio.h>
#define max 20

void quick_sort(int darr[max], int lb, int ub)
{
  int a;
   int up,down;
   int temp;

   if (lb>=ub)
    return;
   a=darr[lb];
   up=ub;
   down=lb;

   while (down < up)
   {
     while (darr[down] <= a)
       down++;
      while (darr[up]>a)
       up--;
      if(down<up)
      {
        temp=darr[down];
         darr[down]=darr[up];
         darr[up]=temp;
      }
   }
   darr[lb]=darr[up];
   darr[up]=a;

   quick_sort(darr,lb,up-1);
   quick_sort(darr,up+1,ub);
}

void main()
{
  int arr[max];                                                                
   int i,n,lb,ub;
   lb=0;

   cout<<"Masukkan banyak data yang ingin diurut: ";
   cin>>n;

   ub=n;
   cout<<"Masukkan data-datanya: \n\n";
   for(i=1;i<=n;i++)
   {
     cout<<"\tdata ke- "<<i<<" : "; cin>>arr[i];
   }

   quick_sort(arr,lb,ub);
   cout<<"\nHasil pengurutan data: ";
   for(i=0; i<n;i++)
    cout<<" "<<arr[i];

   cout<<"\n\nTekan sembarang tombol untuk keluar ";
   getch();
}


Monggo di copasss 

0 komentar:

Posting Komentar

Twitter Delicious Facebook Digg Stumbleupon Favorites More