Thuật Toán Sắp Xếp

Thuật Toán QuickSort
Bài này mình vừa mới viết,xem thử đi nha
Không dùng đệ qui thì chỉ có duy nhất là dùng stack để lưu vết cho chương trình.
Đầu tiên bạn nên viết chương trình đệ qui cho QuickSort.
Từ chương trình đệ qui tiến hành khử đệ qui theo cách sau:
Ý tưởng khử đệ quy như sau:
- Tại lời gọi đệ qui chúng ta cần lưu thông tin của các biến cục bộ vào stack, để sau khi hàm đệ qui hoàn thành thì chương trình khôi phục lại trị cho những thông số cục bộ để làm tiếp cho những câu lệnh sau lời gọi đệ qui.

QuickSort đệ qui:

Code:

void QuickSort_1(int a[],int left,int right){
    int j,k;
    int tmp;
    if(left<right){

        j=left;
        k=right+1;

        do
        {

            do
            {
                j=j++;
            }while (a[j]<a[left]);
     
     
            do
            {
                k=k--;
            }while (a[k]>a[left]);
     
            if(j<k)
            {
                tmp=a[j];
                a[j]=a[k];
                a[k]=tmp;
            }
        }while (j<=k);
     
        tmp=a[left];
        a[left]=a[k];
        a[k]=tmp;
     
        QuickSort_1(a,left,k-1);
        QuickSort_1(a,k+1,right);
    }
}

QuickSort không đệ qui:

Code:

void QuickSort_2(int a[],int left,int right){
    int j,k;
    int tmp;
    Stack<int> leftStack,rightStack,kStack; //lưu giá trị của left,right,k
    int top=0;
L0:
    if(left>=right)
        goto L2;
    else

        j=left;
        k=right+1;

        do
        {

            do
            {
                j=j++;
            }while (a[j]<a[left]);
     
     
            do
            {
                k=k--;
            }while (a[k]>a[left]);
     
            if(j<k)
            {
                tmp=a[j];
                a[j]=a[k];
                a[k]=tmp;
            }
        }while (j<=k);
     
        tmp=a[left];
        a[left]=a[k];
        a[k]=tmp;
     
//Khử đệ qui cho QuickSort_1(a,left,k-1) trong chương trình đệ qui
     
                leftStack.push(left);
        kStack.push(k);
        rightStack.push(right);
        top=top++;
        right=k-1;
        goto L0;
L1:
        left=k+1;
        goto L0;
L2:
        if(top!=0){
            leftStack.top(left);
            leftStack.pop();

            kStack.top(k);
            kStack.pop();

            rightStack.top(right);
            rightStack.pop();

            top=top--;
            goto L1;
        }
}

bài hoàn chỉnh nè:

Code:

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

// Neu ta dung ham dem thoi gian trong thuat toan ta dung ham <time.h>
class Sapxep
{
private:
   int*arr;
public:
   void Nhapmang(int &n);
   void Inmang(int a[],int n);
   void Bubblesort(int a[],int N);
   void Partition(int a[],int F,int L);// phan hoach  tim chi so dau va chi so cuoi
   void Quicksort(int a[],int N); // chu y thuat toan quicksort
};

void Sapxep::Nhapmang(int &n)
{
      cout<<"Nhap vao so phan tu trong Mang :";
      cin>>n;
      arr=new int[n];
   for(int i=0;i<n;i++)
   {
      cout<<"Phan tu thu "<<i+1<<":";
      cin>>arr[i];
   }
}
// Ham in mang
void Sapxep::Inmang(int a[],int n)
{
   for(int i=0;i<n;i++)
   {
      cout<<arr[i];
   }
   cout<<"\n";
}

void Sapxep::Partition(int a[],int F,int L)
{
   int i,j,x;
   if(F>L)
       return;
   int Mid=arr[(F+L)/2];
    i=F;
    j=L;
   do
   {
      while(arr[i]<Mid)
         i++;
      while(arr[j]>Mid)
         j--;
      if(i<=j)
      {
            x = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = x;
         
      }
      i++;
      j--;
   } while(i<=j) ;
         Partition(a,F,j);
          Partition(a,j,L);
         return;


}
void Sapxep::Quicksort(int a[],int N)
{
   Partition(a,0,N-1);
   return;
}

void main()
{
   int n,N;

   // chu y o day ta nen viet ham phat sinh ngau nhien
//   randomize();
//   for(i=0;i<n;i++)
//      arr[i]=random(100);
   int a[1000];
    Sapxep s;
   s.Nhapmang(n);
   cout<<"Mang truoc khi chua sap xep :\n";
   s.Inmang(a,n);
   //cout<<"Sap xep bang Bubble sort: \n";
  // s.Bubblesort(a,n);
//   s.Inmang(a,n);
   cout<<"Sap xep Quicksort:\n";
   s.Quicksort(a,N);
   s.Inmang(a,n);}

Ta đang cần cái này để nghiên cứu chuẩn bị cho đồ án môn học. :arrow: :bounce: :bounce: :bounce: :bounce:

phải đãi tớ một chầu cafe đi>>bạn nào đòng ý thì pm lại nha>>hahhahah>>cho Phương tốn tiền chơi>>hihi 8)