+ Trả lời chủ đề
Hiện kết quả từ 1 tới 1 của 1

Chủ đề: Thuật toán Quick Sort

  1. #1
    Status : ngovanhieu_Alpha đang ẩn
    Tham gia ngày : Aug 2011
    Bài gửi : 200

    Thuật toán Quick Sort

    Thuật toán Quick Sort
    Ý 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.

    Mã:
    #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();
    }
    Lần sửa cuối bởi ngovanhieu_Alpha; 06-08-2011 lúc 03:07 PM

+ Trả lời chủ đề

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
Trang Chủ Việc Làm Gia Sư Gia sư