Jumat, 24 Juni 2011

Program C++ tentang Quick Sort


Quick sort is a sorting method in a programming language. The process of sorting or sorting based on the method of divide and Conqueror. This sort Quick sort data very quickly. But of course this has a shortage of quick sort. For example, the process of sorting performed recursively. Although the process is very fast, but he spent a great memory if the data is sorted a lot. In addition, the quick sort is also not suitable when used to sort the data in the tables are small.

Algoritma :

Procedure quick_sort(output data : larik ; input n : integer)
Deklarasi
i, n, lb,ub   : integer
up,down    : integer
temp          : integer

Deskripsi
read(n)
for i <= to 1 n do
arr[i]
enfor

{ pensortingan akan dilakukan }
if (lb>=ub)
   return
a=darr[lb]
up=ub
down=lb

while (down < up)do
down <=down +1
endwhile

while (darr[down] <= a)do
up <= up – 1
endwhile
if(down<up) then
temp=darr[down]
darr[down]=darr[up]
darr[up]=temp
endif

darr[lb]=darr[up]
darr[up]=a

quick_sort(darr,lb,up-1)
quick_sort(darr,up+1,ub)
endwhile

Berikut kode programnya :

#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();
}


explanation:
Above program describe how the quick sort is a sorting method which is how it works to choose one of the elements of pivot elements (a). This element will be used as a comparison to other elements for stacking with the composition <a,a, and> a ie all the elements to the left of a, the element is smaller than a, while all the elements on the right a, all greater than a.

Ilustration :


0 komentar:

Posting Komentar

Template by:

Free Blog Templates