Thuật toán sắp xếp trộn - Thuật toán Merge 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: 606

  1. Trương Minh Dương

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

    Trong C++ có rất nhiều thuật toán sắp xếp các phần tử từ một danh sách hay một mảng, mình sẽ giới thiệu lần lượt các thuật toán sắp xếp trong C++ cho các bạn tham khảo. Các thuật toán sắp xếp trong C++ bao gồm: Heap sort, Quick sort, Merge sort (sắp xếp trộn, sắp xếp chọn, sắp xếp nổi bọt,...).

    Đầu tiên mình sẽ giới thiệu đến các bạn thuật toán sắp xếp trộn.

    [​IMG]


    Ý tưởng thuật toán:
    Chúng ta sẽ sử dụng mô hình "Chia để Trị" để thiết kế thuật toán sắp xếp bằng phương pháp trộn
    • Chia:
      • Nếu mảng Array rỗng hoặc chỉ có 1 phần tử duy nhất thì trả về chính mảng đó.
      • Ngược lại mảng Array sẽ được chia thành 2 mảng con Array1 và Array2, mỗi mảng chứa n/2 phần tử
    • Đệ qui:
      • Sắp xếp 1 cách đệ qui 2 mảng con Array1 và Array2.
    • Trị:
      • Tạo mảng Array bằng cách trộn 2 mảng con đã được sắp xếp Array1 và Array2 ở bước đệ quy.
    Thiết kế thuật toán Chia để trị

    Mã:
    void merge (int a[], int L, int M, int R){
        int i = L;
        int j = R;
        int k;
        int TA[k];   
        for ( k = L; k <= R; k++){
            if (i > M){
                TA[k] = a[j]; j++;
            } else
                if (j > R){
                TA[k] = a[i]; i++;
            } else {
                if (a[i] < a[j]){
                TA[k] = a[i]; i++;
            } else {
                TA[k] = a[j]; j++;
            }
        }
    }
        for (int k = L; k <= R; k++)
            a[n] = TA[k];
    }
    Thiết kế thuật toán trộn 2 mảng Array con.
    Mã:
    void mergeSort (int a[], int L, int R){
        if (L < R){
            int M = (L + R)/2;
            mergeSort (a, L, M);
            mergeSort (a, M+1, R);
            merge (a, L, M, R);
        }
    }
    Độ phức tạp của thuật toán O(n.log(n)).

    Code hoàn chỉnh của thuật toán sắp xếp trộn - Merge sort

    Mã:
    #include <stdio.h>
    
    int* a;
    int n;
    
    void readData (char* fn){
        FILE* f = fopen (fn,"r");
        fscanf (f,"%d",&n);
        a = new int [n+1];
        for (int i = 1; i < n; i++)
            fscanf (f,"%d",&a[i]);
        fclose (f);
    }
    
    void print (){
        for (int i = 1; i < n; i++)
            printf ("%d  ",a[i]);
    }
    
    void merge (int a[], int L, int M, int R){
        int i = L;
        int j = R;
        int k;
        int TA[k];   
        for ( k = L; k <= R; k++){
            if (i > M){
                TA[k] = a[j]; j++;
            } else
                if (j > R){
                TA[k] = a[i]; i++;
            } else {
                if (a[i] < a[j]){
                TA[k] = a[i]; i++;
            } else {
                TA[k] = a[j]; j++;
            }
        }
    }
        for (int k = L; k <= R; k++)
            a[n] = TA[k];
    }
    
    void mergeSort (int a[], int L, int R){
        if (L < R){
            int M = (L + R)/2;
            mergeSort (a, L, M);
            mergeSort (a, M+1, R);
            merge (a, L, M, R);
        }
    }
    
    void finalize (){
        delete a;
    }
    
    int main (int argc, char** argv){
        char* filename = (argv[1]);
        readData(filename);
        printf ("Truoc khi sap xep: "); print();
        printf ("n");
        mergeSort (a,1,10);
        printf (" Sau khi sap xep: "); print();
        finalize ();
       
    }
    LƯU Ý: Đây là code mình viết trên trình Notepad++ và sử dụng Cygwin (Phần mềm giả lập Linux) để dịch chương trình. Các bạn có thể theo dõi cách sử dụng Cygwin và cách sử dụng Cygwin để dịch chương trình C/C++ tại đây:

    http://minhduongit.com/huong-dan-su-dung-cygwin-dich-chuong-trinh-cc-bang-cygwin/

    Chúc các bạn học tập tốt !!!


    http://www.mediafire.com/?nh5g8be463brqnb
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

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 |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap