1.3 Thiết kế các thuật toán
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 số lincremental]: khi sắp xếp mảng con A[1..j – 1], ta chèn một thành phần A [j] vào đúng chỗ của nó, cho ra mảng con đã sắp xếp A[1..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.
1.3.1 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.
Chia: Chia dãy n-thành phần sẽ được sắp xếp thành hai dãy con, mỗi dãy có n/2 thành phần.
