Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật toán Quick Sort

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Thuật toán Quick Sort

Bài gửi  admin on Sat Apr 17, 2010 8:58 am

Ý tưởng thuật toán: xét dãy n phần tử a_0,a_1,...,a_(n-1).
    Bước 1: chọn khóa pivot = a_(left+right)/2.
    Bước 2: Phân vùng. Những phần tử nhỏ hơn khóa thì nằm bên trái của khóa, những phần tử lớn hơn khóa thì nằm bên phải của khóa và những phần tử bằng khóa có thể nằm bất cứ chỗ nào trên dãy.
    Bước 3: sắp xếp cho cả hai phân vùng mới bên trái và bên phải.


Code:
#include <iostream.h>
#include <conio.h>
#define max 100
void NhapMang(int A[],int n) {
   for(int i=0; i<n; i++) {
      cout<<"nhap Phan tu thu A["<<i<<"] =";
      cin>>A[i];
   }
}
void XuatMang(int A[],int n) {
   cout<<endl;
   for(int i=0; i<n; i++)
      cout<<A[i]<<"\t";
}
void Swap(int &a,int &b) {
   int temp = a;
   a = b;
   b = temp;
}
void QuickSort(int A[], int Left, int Right) {
      int i = Left, j = Right;
      int pivot = A[(Left + Right) / 2];
      /* partition */
      while (i <= j) {
            while (A[i] < pivot)
                  i++;
            while (A[j] > pivot)
                  j--;
            if (i <= j) {
                  Swap(A[i],A[j]);
                  i++;
                  j--;
            }
      }
      /* recursion */
      if (Left < j)
       QuickSort(A, Left, j);
      if (i < Right)
            QuickSort(A, i, Right);

}
void main() {
   int A[max], n;
   clrscr();
   cout<<"Nhap so phan tu:";
   cin>>n;
   NhapMang(A,n);
   cout<<"\nMang vua nhap la:";
   XuatMang(A,n);
   cout<<"\nSap xep theo Quick Sort:";
   QuickSort(A,0,n-1);
   XuatMang(A,n);
   getch();
}

    Hôm nay: Thu Sep 20, 2018 1:29 am