Home » Thuật toán » [Thuật toán] Thuật toán sắp xếp (Phần 4)

[Thuật toán] Thuật toán sắp xếp (Phần 4)

Hôm nay mình xin giới thiệu với các bạn về thuật toán sắp xếp trộn hay còn được gọi là MERGE SORT

Các bạn có thể xem lại [bsbutton text=”Phần 1″ link=”http://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep/” target=”This page” style=”default” theme=”default” size=”normal”][bsbutton text=”Phần 2″ link=”http://motoo.in/lap-trinh-cc-cac-thuat-toan-sap-xep-phan-2/” target=”This page” style=”default” theme=”default” size=”normal”][bsbutton text=”Phần 3″ link=”http://motoo.in/thuat-toan-thuat-toan-sap-xep-phan-3/” target=”This page” style=”default” theme=”default” size=”normal”]

X./ MERGE SORT (Sắp xếp trộn)

1./ Phương pháp chia để trị

Một mô hình thiết kế thuật toán có 3 bước:

  • Chia:
    • Nếu kích thước dữ liệu đầu vào nhỏ hơn một ngưỡng nào đó thì giải trực tiếp
    • Ngược lại chia nhỏ dữ liệu đầu vào thành hai hoặc nhiều tập dữ liệu rời nhau.
  • Đệ qui:
    • Giải một cách đệ qui các bài toán con để lấy lời giải
  • Trị:
    • Kết hợp các lời giải của các bài toán con thành lời giải của bài toán ban đầu

2./ Ý tưởng

Áp 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ử thì trả về chính Array (đã có thứ tự).
    • Ngược lại Array đượ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 đã được sắp xếp Array1 và Array2.

3./ Trộn trực tiếp:

Giải thuật trộn trực tiếp là phương pháp trộn đơn giản nhất. Việc phân hoạch thành các dãy con đơn giản chỉ là tách dãy gồm n phần tử thành n dãy con. Ðòi hỏi của thuật toán về tính có thứ tự của các dãy con luôn được thỏa trong cách phân hoạch này vì dãy gồm một phân tử luôn có thứ tự. Cứ mỗi lần tách rồi trộn, chiều dài của các dãy con sẽ được nhân đôi.

3.1/ Thuật toán:

– Bước 1: // chuẩn bị:

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 Array1, Array2, ., Arrayn thành 2 dãy b và c theo nguyên tắc luân phiên từng nhóm k phần tử:

b = Array1, ., Arrayk, Array2k+1, ., Array3k, .

c = Arrayk+1, ., Array2k,  Array3k+1, ., Array4k, .

– Bước 3 :

Trộn từng cặp dãy con gồm k phần tử của 2 dãy temp_1, temp_2 vào a.

– Bước 4 :

k = k*2;

Nếu k < n thì trở lại bước 2.

Ngược lại: Dừng

3.2/ Cài đặt code C/C++:

 3.3/ Đánh giá

Ta thấy rằng số lần lặp của bước 2 và bước 3 trong thuật toán MergeSort bằng logn do sau mỗi lần lặp giá trị của k tăng lên gấp đôi. Dễ thấy, chi phí thực hiện bước 2 và bước 3 tỉ lệ thuận bới n. Như vậy, chi phí  thực hiện của giải thuật MergeSort sẽ là O(nlogn). Do không sử dụng thông tin nào về đặc tính của dãy cần sắp xếp, nên trong mọi trường hợp của thuật toán chi phí là không đổi. Ðây cũng chính là một trong những nhược điểm lớn của thuật toán

Độ phức tạp trung bình = O(nlogn)

4./ Trộn trực tiếp

Như trong phần đánh giá giải thuật, một trong những nhược điểm lớn của thuật toán Trộn trực tiếp là không tận dụng những thông tin về đặc tính của dãy cần sắp xếp. Ví dụ trường hợp dãy đã có thứ tự sẵn. Chính vì vậy, trong thực tế người ta ít dùng thuật toán trộn trực tiếp mà người ta dùng phiên bản cải tiến của nó. Phiên bản này thường được biết với tên gọi thuật toán trộn tự nhiên (Natural Merge sort).

4.1/ Khái niệm đường ray:

Ðể khảo sát thuật toán trộn tự nhiên, trước tiên ta cần định nghĩa khái niệm đường chạy (run):

Một đường chạy của dãy số a là một dãy con không giảm của cực đại của a. Nghĩa là, đường chạy r = (ai, ai+1,…, aj) phải thỏa điều kiện:

+ 0 ≤ i ≤ j < n , với n là số phần tử của mảng Array

+ Arrayk <= Arrayk+1 , ∀k, i  ≤ k ≤ j

Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 đường chạy (12); (2, 8); (5); (1, 6); (4, 15).

4.2/ Giải thuật:

Bước 1: // Chuẩn bị

r = 0; // r dùng để đếm số dườ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ước 2.1 :

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 2.2 :

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 thì trở lại bước 2;

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

4.3./ Ưu nhược điểm so với Trộn trực tiếp

Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở 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 sau 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 chi có một đường chạy.

Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. Vì vậy thuật toán trộn thường được dùng để sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file.

5./ Video Demo

Share
Share
Free WordPress Themes - Download High-quality Templates