Giải thuật sắp xếp hòa nhập bốn đường
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (160.64 KB, 3 trang )
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ô.
b) Mảng có được sau bước 1.
c) Mảng có được sau bước 2.
d) Mảng có được sau bước 3.
e) Mảng có được sau bước 4. Đây là mảng sắp xếp thô.
f) Mảng đã được sắp xếp hoàn toàn sau khi sắp xếp các dòng.
Minh họa trên cũng cho chúng ta thấy được sự đúng đắn của giải thuật (phần chứng minh
tính đúng đắn xin dành cho các bạn).
Để có được các mảng con sắp xếp thô từ một mảng ban đầu chưa sắp xếp, ta nên dùng
chiến lược chia để trị với kĩ thuật đệ quy.
Procedure Rough_Sort (m, n)
Dữ liệu vào:
Mảng mxn chưa sắp xếp
Dữ liệu ra:
Mảng mxn sắp xếp thô
Các bước thực hiện:
if m > 1 then
begin
B1. Gọi Rough_Sort (m/2,n/2) cho bốn mảng con;
B2. Gọi Four_Way_Merge (m, n);
end;
Vậy, một mảng mxn được sắp xếp hoàn toàn bằng cách làm cho nó trở thành mảng sắp xếp
thô và rồi sắp xếp các dòng của nó.
Procedure Four_Way_ Mergesort (n)
Dữ liệu vào:
Mảng mxn chưa sắp xếp
Dữ liệura:
Mảng mxn đã được sắp xếp
Các bước thực hiện:
B1. Gọi Rough_Sort (m, n)
B2. Sắp xếp các dòng của mảng sắp xếp thô mxn.
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.
