Thuật toán sắp xếp: MERGE SORT và NATURAL MERGE SORT

Ý tưởng

Gọi k là chiều dài của một dãy con

Phân chia dãy ban đầu thành các dãy con có độ dài k, các dãy con này được phân phối luân phiên vào 2 dãy phụ.

Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con của dãy ban đầu, cuối cùng ta sẽ thu được dãy ban đầu có số lượng dãy con giảm phân nửa.

Tăng độ dài k, lặp lại qui trình trên sau một số bước ta sẽ thu được dãy chỉ gồm 1 dãy con, tức là dãy ban đầu đã được sắp xếp.

 

Giải thuật

            Bước 1: k = 1;           // k là chiều dài của dãy con trong bước hiện hành

            Bước 2:

                        Tách dãy a1, a2,…, an thành 2 dãy b, c theo nguyên tắc luân phiên               

           từng nhóm k phần tử:

                                    b = a1,…, ak, a2k+1, …,a3k,…

                                    c = ak+1,…, a2k+1, a3k+1, …,a4k,…

            Bước 3:  Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.

            Bước 4k = k*2;

                           Nếu k < n : Lặp lại bước 2.

                           Ngược lại: Dừng.

NATURAL MERGE SORT

Ý tưởng

Thuật toán Natural Merge Sort khác thuật toán Merge Sort ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy, ta chỉ cần biết số đường chạy của a sao lần phân hoạch cuối cùng là có thể biết thời điểm dừng của thuật toán vì dãy đã có thứ tự là dãy chỉ có một đường chạy.

 

Thuật toán

            Bước 1: r = 0;           // r  dùng để đếm số đường chạy.

            Bước 2:

                        Tách dãy a1, a2,…, an thành 2 dãy b, c theo nguyên tắc luân phiên                

           từng đường chạy.

                                    b = a1,…, ak, a2k+1, …,a3k,…

                                    c = ak+1,…, a2k+1, a3k+1, …,a4k,…

                        Bước 21:

                                    Phân phối cho b một đường chạy; r = r + 1;

                                    Nếu a còn phần tử chưa phân phối

                                                Phân phối cho c một đường chạy; r = r + 1;

            Bước 22:

                                    Nếu a còn phần tử: quay lại bước 21.

            Bước 3:  Trộn từng cặp đường chạy của 2 dãy b, c vào a.

            Bước 4:  Nếu r ≥ 2 : Lặp lại bước 2.

                            Ngược lại: Dừng.

 

Chủ đề liên quan
Thuật toán sắp xếp: MERGE SORT và NATURAL MERGE SORT

Cùng chuyên mục

Xem nhiều hôm nay