Giải thuật sắp xếp hoà nhập bốn đường
Võ Công Chương
Có nhiều phương pháp sắp xếp. Song, tùy thuộc vào sự tổ chức của dữ liệu, người ta chọn
phương pháp sắp xếp sao cho phù hợp. Dưới đây, tôi xin chia sẻ với bạn đọc phương pháp
sắp xếp hòa nhập bốn đường (4-Way Mergesort) trên mảng 2 chiều.
1. Thiết kế giải thuật
Định nghĩa:
Một mảng 2 chiều mxn gọi là mảng sắp xếp thô (roughly sorted) nếu ta chỉ cần sắp xếp các
dòng của nó thì toàn bộ mảng sẽ được sắp xếp hoàn toàn.
Vậy, trong mảng sắp xếp thô, mỗi phần tử của mảng đã nằm đúng trên dòng của nó.
Ví dụ 1:
ý tưởng của sắp xếp hòa nhập bốn đường là hòa nhập bốn mảng sắp xếp thô m/2xn/2 lại
với nhau để được một mảng sắp xếp thô mxn. (ở đây, ta mặc định là sắp tăng dần)
Procedure Four_Way_Merge (m, n)
Dữ liệu vào:
Mảng mxn thỏa mãn bốn mảng con m/2xn/2 của nó là sắp xếp thô.
Dữ liệu ra:
Mảng sắp xếp thô mxn.
Các bước thực hiện:
B1. Sắp xếp các dòng của bốn mảng con theo cách:
- Sắp xếp giảm dần với mảng con có chỉ số nhỏ hơn,
- Sắp xếp tăng dần với mảng con có chỉ số lớn hơn.
B2. Sắp xếp tăng dần các cột của mảng mxn.
B3. Sắp xếp các dòng của mảng mxn theo cách:
- Dòng lẻ thì sắp xếp tăng dần,
- Dòng chẵn thì sắp xếp giảm dần.
B4. Sắp xếp tăng dần các cột của mảng mxn.
Ví dụ 2:
Với m =5 và n =5, mỗi mảng con sắp xếp thô có kích thước là 2x2. Các bước thực hiện giải
thuật như sau:
Hình 2: a) Mảng ban đầu có 4 mảng con sắp xếp thô.

2. Phân tích giải thuật
Ta thử phân tích độ phức tạp của giải thuật khi sắp xếp một mảng nxn.
Ta có thể sắp xếp mỗi một dòng n phần tử theo phương pháp sắp xếp nổi bọt. Vậy, như
bạn đã biết, trong trường hợp xấu nhất ta phải mất thời gian là n(n-1)/2. Gọi việc sắp xếp
một dòng hay một cột là một bước sắp xếp thì việc sắp xếp n dòng hoặc n cột của mảng
nxn phải mất n bước. Trong thủ tục Four_Way_Merge, số lượng các bước là:
B1: n/2 bước
B2: n bước
B3: n bước
B4: n/2 bước
Tổng: 3n bước.
Chú ý rằng, B4 chỉ cần n/2 bước bởi vì mỗi cột đã được chia thành 2 phần (trên và dưới)
bởi 4 mảng con ban đầu, nên ta chỉ cần sắp xếp trong nội bộ 2 phần của mỗi cột đó.
Việc gọi đệ quy Four_Way_Merge trong Rough_Sort mất 3n+3n/2+3n/4+…+3 ≤ 6n bước.
Do vậy, cộng thêm việc sắp xếp các dòng của mảng nxn trong Four_Way_Mergesort ta có
tổng thời gian của giải thuật là: T(n)≤7n bước. Mỗi bước mất thời gian ít nhất là n(n-1)/2
nên T(n) ≤7n
2
(n-1)/2. Với kích thước của mảng hai chiều là nxn thì độ phức tạp tính toán
của giải thuật là: O(n
3/2
).
3. Kết luận
Đến đây, bạn đã biết được giải thuật sắp xếp hòa nhập bốn đường là gì. Độ phức tạp của
nó là chấp nhận được, cụ thể là O(n
3/2
). Bạn cũng sẽ biết cách cài đặt giải thuật này một khi
bạn muốn sắp xếp một mảng 2 chiều.