Thuật toán sắp xếp phân đoạn – Thuật toán Quick sort trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 898

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Tương tự như heapsort hay các thuật toán sắp xếp nhanh khác - quicksort cũng là 1 thuật toán có thời gian thực hiện khá nhanh (tương tự như heapsort).

    [​IMG]



    Ý tưởng của thuật toán:

    Để sắp xếp dãy khóa k1,k2,...kn coi như sắp xếp đoạn có chỉ số từ 1 đến n trong dãy khóa đó. Để sắp xếp 1 đoạn trong dãy khóa đó, nếu đoạn có 1 phần tử ta sẽ giữ nguyên, nếu có trên 2 phần tử, ta sẽ chọn ngẫu nhiên 1 phần tử-gọi là key. Mọi khóa trong đoạn mà nhỏ hơn key sẽ được chuyển về phía trước key, mọi khóa lớn hơn key sẽ được chuyển về phía sau của key. Sau khi hoán chuyển như vậy, đoạn đang xét sẽ được chia làm 2 đoạn mà mọi khóa trong đoạn đầu đều <= key và mọi khóa trong đoạn sau đều >= key. Như vậy ta sẽ tiếp tục các thao tác trên với đoạn đầu và đoạn cuối để có được 1 dãy hoàn chỉnh.




    http://www.mediafire.com/?nh5g8be463brqnb

    Trình diễn thuật toán Quick Sort

    [​IMG]

    Hàm quicksort:

    Mã:
    void quicksort(int a[],int l, int r){
        int i=l, j=r;                                //Khởi tạo chỉ số trái và phải
        int key=a[(l+r)/2];                           //Lấy giá trị key=phần tử ở giữa
        while (i<=j){                               
            while (a[i]<key) i++;                       //Tìm đến giá trị bên trái > key
            while (a[j]>key) j--;                       //Tìm đến giá trị bên phải < key
            if (i<=j ){                                 //Đổi vị trí 2 giá  trị
                int tmp=a[i];
                a[i]=a[j];
                a[j]=tmp;
                i++;
                j--;
                }
                }
        while (i<=j)
        if (l < j)
            quicksort(a, l, j);                   //Gọi đệ quy lại đoạn bên trái
        if (i < r)
            quicksort(a, i, r);                   //Gọi đệ quy lại đoạn bên phải
    }

    Chương trình quicksort hoàn chỉnh:

    Mã:
    #include <stdio.h>
    int n;
    void quicksort(int a[],int l, int r){
        int i=l;
        int j=r;
        int tb=a[(l+r)/2];
        while(i<=j){
            while(a[i]<tb) i++;
            while (a[j]>tb) j--;
            if (i<=j){
                int key=a[i];
                a[i]=a[j];
                a[j]=key;
                i++;
                j--;
            }
        }
        if(l<j) quicksort(a,l,j);
        if(i<r) quicksort (a,i,r);
        }
    int main() {
        int a[100000];
        printf("Nhap so phan tu cua mang n"); scanf("%d",&n);
        for (int i=0;i<n;i++){
            printf("a[%d]=",i+1); scanf("%d",&a[i]);
            printf("n");
            }
    
       
    
        quicksort(a,0,n-1);
        printf("Mang sap xep la: n");
    for (int i=0;i<n;i++)
            printf("%d  ",a[i]);
    
    
    }
    FILE dữ liệu đầu vào:
    Mã:
    9
    9 5 3 4 8 6 7 1 2
    Đọc thêm: Thuật toán sắp xếp Heapsort
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Sitemap