Thuật toán sắp xếp vun đống – Thuật toán Heap 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: 2,994

  1. Ở bài trước, mình đã giới thiệu đến các bạn thuật toán sắp xếp trộn. Bài này sẽ là thuật toán sắp xếp cũng được sử dụng rất nhiều đó là thuật toán sắp xếp vun đống (Heap Sort). Mời các bạn theo dõi mình thiết lập thuật toán ở bên dưới.

    [​IMG]




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

    Sắp xếp vun đống là gì?

    Sắp xếp vun đống (Heapsort) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống.

    Ý tưởng thuật toán

    Mảng A[1...n] (Mảng gồm n phần tử)

    Để giải quyết bài toán, chúng ta cần có 1 cây nhị phân đầy đủ.

    Giá trị của nút lá phải nhỏ hơn hoặc bằng giá trị của nút cha.

    Nút cha A có 2 nút con là A và A[2i + 1].


    Thuật toán được mô tả như sau:

    - Xây dựng Heap sao cho với mọi nút cha thì đều có 2 nút lá có giá trị nhỏ hơn hoặc bằng.

    - Hoán vị nút gốc với nút thứ n –1 và xây dựng lại Heap mới với n–2 nút và tiếp tục hoán vị nút gốc với nút lá cuối của cây mới sau n–2 bước ta sẽ thu được danh sách được sắp xếp theo thứ tự.

    Cài đặt thuật toán
    //Hoán vị nút cha thứ i phải lớn hơn nút lá
    Mã:
    void heapify (int* a, int i, int n){
        int L = 2*i;
        int R = 2*i + 1;
        int max  = i;
        if (L <= n && a[L] > a[i]) max = L;
        if (R <= n && a[R] > a[max]) max = R;
        if (max != i){
            swap (a[i], a[max]);
            heapify(a, max, n);
        }
    }
    //Xây dựng Heap sao cho mọi nút lá đều nhỏ hơn hoặc bằng nút cha.

    Mã:
    void buildHeap(int a[], int n){
        for (int i = n/2; i >= 1; i--){
            heapify (a, i, n);
        }
    }
    Mã:
    void heapSort (int a[], int n){
        buildHeap (a, n);
        for (int i = n; i > 1; i--){
            swap (a[1], a[i]);
            heapify(a, 1, i-1);
        } print();
    }

    Thuật toán sắp xếp vun đống đầy đủ:

    Mã:
    #include <stdio.h>
    #include <algorithm>
    
    using namespace std;
    
    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 heapify (int* a, int i, int n){
        int L = 2*i;
        int R = 2*i + 1;
        int max  = i;
        if (L <= n && a[L] > a[i]) max = L;
        if (R <= n && a[R] > a[max]) max = R;
        if (max != i){
            swap (a[i], a[max]);
            heapify(a, max, n);
        }
    }
    
    void buildHeap(int a[], int n){
        for (int i = n/2; i >= 1; i--){
            heapify (a, i, n);
        }
    }
    
    void heapSort (int a[], int n){
        buildHeap (a, n);
        for (int i = n; i > 1; i--){
            swap (a[1], a[i]);
            heapify(a, 1, i-1);
        } print();
    }
    
    void finalize (){
        delete a;
    }
    
    int main (int argc, char** argv){
        char* filename = argv[1];
        readData(filename);
        printf ("Before sorting: "); print();
        printf ("n");
        printf ("After sorting: ");
        heapSort(a,n);
        finalize();
    }
    File dữ liệu:
    Mã:
    9
    9 5 3 4 8 6 7 1 2

    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/
     
    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 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 | Tư vấn du học EduTrust | Bếp từ GGM Italia | Bếp từ | Bếp từ nhập khẩu | Máy hút mùi |Sitemap