Có nhiều cách để thiết kế các thuật toán. Phương pháp sắp xếp chèn sử dụng cách tiếp cận gia^[incremental]: khi sáp xếp mảng con A[\.j – 1], ta chèn một thành phần A[ý] vào đúng chỗ của nó, cho ra mảng con đã sắp xếp A[l.j].
Trong đoạn này, ta xem xét một cách tiếp cận thiết kế khác, có tên “chia để trị” [“divide-and-conquer”]. Ta sẽ dùng kỹ thuật chia để trị để thiết kế một thuật toán sáp xếp có thời gian thực hiện trường hợp xấu nhất nhỏ hơn nhiều so với kiểu sáp xếp chèn. Các thuật toán chia để trị có một ưu điểm đó là các thời gian thực hiện của chúng thường dễ xác định bằng các kỹ thuật mô tả trong Chương 4.
Cách tiếp cận chia để trị
Có nhiều thuật toán hữu ích theo cấu trúc đệ quy : để giải quyết một bài toán nhất định, chúng tự gợi theo đệ quy một hay nhiều lần để đối phó với các bài toán con có liên quan mật thiết. Các thuật toán này thường theo cách tiếp cận chia để trị: chúng tách nhỏ bài toán thành vài bài toán con tương tự như bài toán ban đầu song có kích cỡ nhỏ hơn, giải quyết các bài toán con một cách đệ quy, rồi tổ hợp các nghiệm này để tạo một nghiệm cho bài toán ban đầu.
Kiểu mẫu chia để trị liên quan đến ba bước tại mỗi cấp của đệ quy:
Chia bài toán thành một số bài toán con.
“Trị” các bài toán con bằng cách giải quyết chúng một cách đệ quy. Tuy nhiên, nếu các bài toán con đủ nhỏ, ta chỉ việc giải quyết các bài toán con theo cách đơn giản.
Tể hợp các nghiệm của các bài toán con thành nghiệm cho bài toán ban đầu.
Thuật toán sắp xếp trộn[merge sort] theo sát kiểu mẫu chia để trị. Theo trực giác, nó hoạt động như sau.
Chỉa: Chia dãy «-thành phần sẽđược sắp xếp thành hai dăy con, mỗi . dãy có «/2 thành phần.
Trị: Dùng kỹ thuật sắp xếp trộn để sắp xếp hai dãy con theo đệ quy.
Tổ hợp: Hợp nhất hai dãy con đã sắp xếp để cho ra đáp án đã sắp xếp.
Lưu ý, đệ quy sẽ “hóa ra công cốc” khi dãy sáp xếp có chiều dài là 1, trong trường hợp đó không có gì được thực hiện, bởi mọi dãy có chiều dài 1 đã theo một thứ tự sáp xếp sấn.
Tác vụ chính của thuật toán sắp xếp trộn đó là tiến trinh trộn hai dày đã sấp xếp trong bước “tổ hợp”. Để thực hiện tiến trình trộn, ta dùng một thủ tục phụ trợ MERGE(A, p7 q, /*), ởđó A là một mảng và p, q, và r là các chỉ mục đánh sô” các thành phần của máng sao cho p < q < r. Thủ tục mặc nhận các mảng con A[p..q] và A[q + l..r] nằm theo thứ tự sắp xếp. Nó trộn[merges] chúng để tạo thành chỉ một mdng con sắp xếp thay thế mảng con hiện hành A[p..r].
Mặc dù để dành mã giả làm bài tập (xem Bài tập 1.3-2), song ta cũng dễ dàng hình dung một thủ tục MERGE bỏ ra một thời gian 0 (n), ở đó n = r – p + 1 là số lượng thành phần đang được trộn. Trở về chủ đề chơi bài, giả sử ta có hai đống lá bài tung ngửa trên bàn. Mỗi đống được sắp xếp, với lá bài nhỏnhâ”t nằm trên cùng. Ta muốn trộn hai đống thành chỉ một đông kết xuâ”t đã sắp xếp, nằm tung sấp trên bàn. Bước căn bản bao gồm tiến trình chọn lá nhỏ hơn trong hai lá bài trên đầu của cdc đô”ng tung ngửa, gỡ bỏ nó ra khỏi đống đó (bày ra một lá bài mới trên đầu), và đặt lá bài này tung sâp lên trên đống kết xuất. Ta lặp lại bước này cho đến khi một đống đầu vào trống rỗng, vào lúc đó ta chỉ việc lấy đông đầu vào còn lại và đặt nó tung sấp lên trên đông kết xuát. về mặt tính toán, mỗi bước căn bản bỏ ra một thời gian bâ”t biến, bởi ta chỉ đang kiểm tra hai lá bài trên cùng. Do ta thực hiện tối đa n bước căn bản, nên tiến trình trộn chiếm 000 thời gian.
Giờ đây, có thể dùng thủ tục MERGE như một chương trình con trong thuật toán sắp xếp trộn. Thủ tục MERGE-SORT (A, p, r) sắp xếp các thành phần trong mảng con A ịp..rị Nếu p>r, mảng con có tối đa một thành phần và do đó đã được sắp xếp san. Bằng không, bước chia đơn giản tính toán một chỉ sốq phân hoạch A[p..r\ thành hai mảng con: A[p..q\ chứa \n/í\ thành phần, và A[q +1 ..rị chứa Vn/l\ thành phần .
MERGE-SORT (A, p, r)
1 if p <r
2 then q<— Lo? + r)/2j
3 MERGE-SORT(A,p,ợ)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, /7, q, r)
Để sắp xếp nguyên cả dãy A = <A[l],A[2],…,A[/?]>, ta gọi MERGE- SORT(A, 1, ỉength[A]), ở đó một lần nữa length[A] = n. Nếu xem xét phép toán của thủ tục từ dưới lên khi n là một lũy thừa của hai, thuật toán bao gồm tiến trình trộn các cặp dãy 1-mục để tạo thành các dãy sắp xếp có chiều dài 2, tiến trình trộn các cặp dãy có chiều dài 2 để tạo thành các dãy sắp xếp có chiều dài 4, và vân vân, cho đến khi hai dãy có chiều dài rưlúược trộn để tạo thành dãy sắp xếp chung cuộc có chiều dài n. Hình 1.3 minh họa tiến trình này.