SẮP XẾP TRỘN THÍCH ỨNG (ADAPTIVE MERGE SORT)
Adaptive Merge Sort thực hiện trộn các danh sách con đã sắp xếp như merge sort. Tuy nhiên, kích thước danh sách con ban đầu phụ thuộc vào sự tồn tại của thứ tự trong danh sách phần tử thay vì có danh sách con kích thước 1. Ví dụ, xem danh sách trong hình.
Nó bao gồm 2 danh sách con đã sắp xếp:
- Danh sách con 1: 16, 15, 14, 13.
- Danh sách con 2: 9, 10, 11, 12.
Danh sách con 1 đã sắp xếp nhưng theo thứ tự ngược. Do đó, danh sách con 1 được đảo ngược như hình.
Một khi các danh sách con được tìm thấy, quá trình trộn bắt đầu. Adaptive merge sort bắt đầu trộn các danh sách con. Adaptive merge sort chỉ cần một bước trộn vì chỉ có 2 danh sách con. Kết quả trộn như hình.
Ý tưởng thiết kế (Design Idea)
- Bắt đầu bằng cách tìm các danh sách con đã sắp xếp theo thứ tự yêu cầu hoặc ngược.
- Nếu tồn tại danh sách con nào có phần tử theo thứ tự ngược, đảo ngược danh sách con đó bằng cách đổi chỗ phần tử 1 với cuối, 2 với lפני cuối, và tiếp tục.
- Tiếp tục trộn các danh sách con để tạo danh sách con mới cho đến khi chỉ còn 1 danh sách con.
Phân tích Adaptive Merge Sort
Adaptive merge sort thay vì bắt đầu với danh sách con kích thước 1, tìm danh sách con đã sắp xếp theo thứ tự yêu cầu hoặc ngược. Kích thước danh sách con ban đầu tối thiểu 2 và tối đa m (m là số phần tử).
Tuy nhiên, nếu danh sách con chứa phần tử theo thứ tự ngược, nó đảo ngược danh sách trước khi bắt đầu trộn. Việc đảo ngược yêu cầu (m/2) phép đổi chỗ.
Trường hợp tốt nhất (Best Case)
Nếu danh sách đã theo thứ tự sắp xếp hoặc ngược, Adaptive merge sort chỉ có một danh sách và không cần thao tác trộn. Tuy nhiên, phát hiện danh sách đã sắp xếp yêu cầu O(m) phép so sánh và (m/2) phép đổi chỗ nếu sắp xếp ngược. Điều này làm Adaptive Merge sort thích ứng (adaptive) ngay cả khi danh sách sắp xếp ngược.
Do đó, độ phức tạp thời gian trường hợp tốt tính như sau:
T(m) = (m-1) + (m/2) T(m) = (2m-2+m)/2 T(m) = O(m).
Tuy nhiên, Adaptive merge sort dùng thêm không gian O(m) so với merge sort.
Trường hợp xấu nhất (Worst Case)
Adaptive merge sort tìm danh sách con đã sắp xếp theo thứ tự yêu cầu hoặc ngược. Tuy nhiên, trường hợp xấu nhất không có thứ tự phần tử một phần hay toàn phần. Do đó, danh sách con ban đầu kích thước 2. Khi tìm thấy danh sách con, quá trình trộn bắt đầu.
- Trộn danh sách con kích thước 2 → danh sách con sắp xếp kích thước 4.
- Trộn kích thước 4 → kích thước 8.
- Quá trình trộn tiếp tục cho đến 2k < m, với k là bước trộn thứ k.
Vì các bước trộn trường hợp xấu của Adaptive merge sort giống merge sort, độ phức tạp thời gian trường hợp xấu cũng giống merge sort:
T(m) = O(m log m).