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.

rút gọn link kiếm tiền

Lượt xem: 1,446

  1. 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ị


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

    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 !!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

Chia sẻ trang này

rao vặt thần tốc
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 PC |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 | Hack Like Facebook | Du học | http://edutrust.edu.vn | Du học Anh | Du học Mỹ | Du học Úc | Du học Malta | Du học Síp | Du học hè Canada | Du học Canada SDS | Tư vấn du học EduTrust |Rao vặt thần tốc |rao vặt miễn phí |diễn đàn rao vặt | Rút gọn link | Rút gọn link kiếm tiền | URL Shortener | Short URL | Link Bit | Bit Link | lbit.me |Sitemap