Chia bài toán thành các phần rồi ghép lời giải

Lan cần kiểm tra 50 000 kết quả theo thứ tự nộp bài. Bạn muốn đếm những cặp bị đảo thứ tự, nhưng so sánh từng cặp có thể cần hơn một tỉ phép kiểm tra. Liệu có thể xử lý từng phần rồi ghép thông tin mà không bỏ sót cặp nào?

Mỗi lần chia cần đoạn nhỏ hơn và một cách ghép rõ ràng

Chia để trị (divide and conquer) giải bài toán bằng ba bước. Đầu tiên, chia dữ liệu thành các phần nhỏ hơn. Tiếp theo, giải từng phần cùng dạng. Cuối cùng, ghép các kết quả để trả lời bài toán ban đầu.

Ví dụ, để tìm giá trị nhỏ nhất, ta tìm giá trị nhỏ nhất ở mỗi nửa rồi lấy số nhỏ hơn. Với một phần tử, kết quả đã có sẵn. Đây là trường hợp cơ sở (base case), nơi đệ quy dừng lại.

Chương trình sau tìm số nhỏ nhất trong dãy gồm năm phần tử:

def minimum(a, left, right):
    if right - left == 1:
        return a[left]
    mid = (left + right) // 2
    x = minimum(a, left, mid)
    y = minimum(a, mid, right)
    return min(x, y)

a = [8, 3, 7, -2, 5]
print(minimum(a, 0, len(a)))

-2

Kết quả là giá trị nhỏ nhất của toàn dãy. Mỗi phần tử thuộc đúng một nửa, nên số nhỏ nhất toàn đoạn phải là số nhỏ nhất của một trong hai nửa. Hàm nhận đoạn không rỗng; nếu cho phép dãy rỗng, cần quy định riêng kết quả của trường hợp đó.

Ở đây có n lá và n - 1 lần ghép, nên thời gian là O(n). Cách duyệt một vòng cũng đạt O(n) và thường đơn giản hơn. Mục đích ví dụ là nhận ra vai trò của chia, dừng và ghép.

Đoạn nửa mở giúp chia không sót và không lặp chỉ số

Đoạn nửa mở (half-open interval) [left, right) gồm chỉ số từ left đến right - 1. Độ dài là right - left; khi hai đầu bằng nhau, đoạn rỗng. Đặt mid = (left + right) // 2 để chia thành [left, mid) và [mid, right).

Đoạn trái kết thúc trước mid; đoạn phải bắt đầu tại mid. Không phần tử nào xuất hiện trong cả hai nửa. Đoạn dài lẻ được chia thành hai nửa lệch nhau một phần tử.

Trong hình, biên phải bằng 5 nằm ngay sau ô cuối nên không có mũi tên trên ô. Độ dài hai nửa là 2 và 3; cộng lại vẫn bằng độ dài đoạn ban đầu. Cách viết này cũng cho phép một đoạn rỗng khi hai biên trùng nhau.

Đoạn mã sau hiển thị hai nửa và độ dài của chúng:

a = [8, 3, 7, -2, 5]
left, right = 0, len(a)
mid = (left + right) // 2
print(a[left:mid], a[mid:right])
print(mid - left, right - mid)

[8, 3] [7, -2, 5]
2 3

Khi đoạn chỉ có một phần tử, mid có thể bằng left. Nếu vẫn gọi tiếp trên cùng đoạn, đệ quy không tiến triển. Vì vậy, phép sắp xếp bên dưới dừng khi độ dài không quá một.

Một đoạn rỗng và một đoạn một phần tử đều đã tăng dần. Ví dụ sau kiểm tra điều kiện dừng trên hai đầu vào đó:

for a in ([], [9], [2, 1]):
    print(a, len(a) <= 1)

[] True
[9] True
[2, 1] False

Hai dòng đầu cho điều kiện đúng; dòng cuối cần xử lý tiếp. Quy ước đoạn phải được giữ thống nhất ở cả lúc gọi và lúc ghép.

Trộn hai nửa đã tăng để sắp xếp toàn đoạn

Sắp xếp trộn (merge sort) chia dãy đến khi mỗi đoạn dài tối đa một. Khi quay về, phép trộn (merge) ghép hai dãy đã tăng thành một dãy tăng. So sánh hai phần tử đầu chưa dùng; đưa phần tử nhỏ hơn vào kết quả.

Với hai dãy [2, 5, 8] và [1, 5, 7], đầu tiên chọn 1. Sau đó chọn 2; hai đầu đang xét trở thành 5 và 5. Khi bằng nhau, chọn phần tử bên trái trước để giữ thứ tự tương đối của các khóa bằng nhau.

Hàm dưới đây trộn hai danh sách; phần còn lại được nối sau khi một bên hết:

def merge(left, right):
    i = j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge([2, 5, 8], [1, 5, 7]))

[1, 2, 5, 5, 7, 8]

Mỗi lần chọn, phần tử được chọn nhỏ nhất trong các phần tử chưa dùng. Điều đó đúng vì mỗi nửa đã tăng. Khi một bên hết, phần còn lại của bên kia đã tăng và không nhỏ hơn phần tử vừa chọn.

Sau đây là chương trình hoàn chỉnh, đọc một dãy và in dãy tăng:

6
6 2 5 2 -1 4

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

n = int(input())
a = list(map(int, input().split()))
print(*merge_sort(a))

-1 2 2 4 5 6

Hai lời gọi con trả về hai dãy tăng. Lập luận phép trộn cho thấy kết quả ghép cũng tăng. Trường hợp cơ sở đúng, nên lập luận này áp dụng từ các đoạn nhỏ tới toàn dãy.

Mỗi tầng xử lý tối đa n phần tử, và có khoảng log₂ n tầng. Vì vậy thời gian là O(n log n). Với n = 50 000, có khoảng 16 tầng chia, tương ứng cỡ 800 000 lượt phần tử qua các tầng. Danh sách tạm và lát cắt cần thêm bộ nhớ O(n) tại một thời điểm; Python còn có chi phí cấp phát.

Tính ổn định (stability) có ích khi mỗi phần tử mang thêm thông tin. Hai bạn cùng điểm sẽ giữ thứ tự ban đầu nếu trộn chọn bên trái trước khi điểm bằng nhau. Đoạn sau minh họa quy tắc chọn theo điểm, không so tên:

left = [(7, 'An'), (8, 'Bình')]
right = [(7, 'Chi'), (9, 'Dũng')]
i = j = 0
out = []
while i < len(left) and j < len(right):
    if left[i][0] <= right[j][0]:
        out.append(left[i])
        i += 1
    else:
        out.append(right[j])
        j += 1
out.extend(left[i:])
out.extend(right[j:])
print(out)

[(7, 'An'), (7, 'Chi'), (8, 'Bình'), (9, 'Dũng')]

An đứng trước Chi vì hai bạn bằng điểm và An thuộc nửa trái. Nếu chỉ cần sắp xếp thông thường trong Python, sorted thường là lựa chọn thực tế. Phép trộn tự cài đặc biệt hữu ích khi cần tính thêm thông tin trong lúc ghép.

Đếm nhiều nghịch thế cùng lúc nhờ hai nửa đã tăng

Một nghịch thế (inversion) là cặp chỉ số (i, j) với i < j và a[i] > a[j]. Cặp bằng nhau không được tính. Duyệt mọi cặp cần n(n - 1) / 2 phép so sánh; với n = 50 000, con số này là 1 249 975 000.

Sau khi chia, mỗi cặp thuộc đúng một loại: cả hai ở trái, cả hai ở phải, hoặc phần tử đầu ở trái và phần tử sau ở phải. Hai lời gọi con đếm hai loại đầu. Phép trộn đếm loại thứ ba, gọi là nghịch thế chéo.

Giả sử nửa trái đã sắp thành [2, 4, 7], nửa phải thành [1, 3, 6]. Khi chọn 1, cả ba phần tử trái còn lại đều lớn hơn 1, nên cộng ba. Khi chọn 3, chỉ còn 4 và 7, nên cộng hai. Khi chọn 6, chỉ còn 7, nên cộng một.

Bảng sau do chương trình tạo ra từ chính hai nửa đó:

Phần tử phải đang xét nhỏ hơn mọi phần tử trái còn lại vì nửa trái đã tăng. Mọi phần tử trái đều xuất hiện trước phần tử phải trong dãy gốc. Do đó len(left) - i là đúng số cặp mới, không phải chỉ một cặp.

Hàm sau vừa trả về dãy đã sắp vừa trả về số nghịch thế:

def count_and_sort(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = count_and_sort(a[:mid])
    right, y = count_and_sort(a[mid:])
    i = j = 0
    result = []
    count = x + y
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += len(left) - i
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

a = [4, 2, 5, 1, 3, 2]
ordered, inversions = count_and_sort(a)
print(ordered)
print(inversions)

[1, 2, 2, 3, 4, 5]
9

Mỗi cặp được đếm đúng tại lần chia đầu tiên tách hai chỉ số sang hai nửa. Cặp trong cùng một nửa được lời gọi con xử lý. Nhánh <= giữ các giá trị bằng nhau khỏi bị tính nhầm. Thời gian vẫn là O(n log n) vì mỗi lần trộn chỉ thêm phép cộng hằng số cho mỗi phần tử.

Với dãy ngắn, một cách độc lập để kiểm tra là liệt kê mọi cặp chỉ số:

a = [4, 2, 5, 1, 3, 2]
pairs = [(i, j) for i in range(len(a))
         for j in range(i + 1, len(a)) if a[i] > a[j]]
print(pairs)
print(len(pairs))

[(0, 1), (0, 3), (0, 4), (0, 5), (1, 3), (2, 3), (2, 4), (2, 5), (4, 5)]
9

Cách chậm này hữu ích để tự kiểm trên dãy nhỏ có số âm và số trùng. Không nên dùng nó cho đầu vào lớn vì chi phí tăng theo n².

Đoạn có tổng lớn nhất nằm bên trái, bên phải hoặc qua giữa

Xét một dãy không rỗng và yêu cầu đoạn con liên tiếp cũng không rỗng. Sau khi chia tại mid, một đoạn bất kỳ hoặc nằm hoàn toàn bên trái, hoặc nằm hoàn toàn bên phải, hoặc chứa phần tử của cả hai bên. Ba trường hợp này bao phủ mọi đáp án.

Với đoạn đi qua giữa, phần bên trái phải là một hậu tố (suffix) kết thúc ngay trước mid. Phần bên phải phải là một tiền tố (prefix) bắt đầu tại mid. Lấy hậu tố có tổng lớn nhất cộng với tiền tố có tổng lớn nhất sẽ cho đoạn qua giữa tốt nhất.

Ví dụ dưới đây xử lý [-4, 3, -1, 5, -8, 2]. Hai vòng quét tính tổng các phần sát điểm chia:

a = [-4, 3, -1, 5, -8, 2]
mid = len(a) // 2
s = 0
left_best = None
for i in range(mid - 1, -1, -1):
    s += a[i]
    left_best = s if left_best is None else max(left_best, s)
s = 0
right_best = None
for i in range(mid, len(a)):
    s += a[i]
    right_best = s if right_best is None else max(right_best, s)
print(left_best, right_best, left_best + right_best)

2 5 7

Hai phần được chọn phải không rỗng. Khởi tạo bằng None thay vì 0 giúp không vô tình chọn đoạn rỗng khi mọi số đều âm.

Chương trình đầy đủ so sánh kết quả của cả ba trường hợp:

def best(a, left, right):
    if right - left == 1:
        return a[left]
    mid = (left + right) // 2
    x = best(a, left, mid)
    y = best(a, mid, right)
    s = 0
    suffix = None
    for i in range(mid - 1, left - 1, -1):
        s += a[i]
        suffix = s if suffix is None else max(suffix, s)
    s = 0
    prefix = None
    for i in range(mid, right):
        s += a[i]
        prefix = s if prefix is None else max(prefix, s)
    return max(x, y, suffix + prefix)

for a in ([-4, 3, -1, 5, -8, 2], [-8, -3, -5], [6]):
    print(best(a, 0, len(a)))

7
-3
6

Ở dãy toàn âm, đáp án là phần tử lớn nhất, không phải 0. Mỗi tầng quét tổng cộng n phần tử, nên thời gian O(n log n) và ngăn xếp sâu O(log n). Với 50 000 số, khoảng 16 tầng quét là cỡ 800 000 lượt. Có thuật toán một lượt O(n) cho bài toán này; ở đây ta luyện cách ghép ba trường hợp.

Chi phí của lời giải phụ thuộc cả số nhánh lẫn việc ghép

Trong cây đệ quy của sắp xếp trộn, mỗi nút chia thành hai đoạn gần bằng nhau. Ở cùng một tầng, các đoạn không giao nhau và phủ dữ liệu ban đầu. Vì thế tổng độ dài tại mỗi tầng là n, dù số nút tăng lên.

Với tám phần tử, các tầng có tổng độ dài lần lượt là tám, tám và tám. Lớp lá tiếp theo gồm tám đoạn một phần tử. Với kích thước không phải lũy thừa của hai, độ sâu hai nhánh có thể lệch một, nhưng chặn O(n log n) vẫn đúng.

Không nên kết luận mọi đệ quy chia đôi đều chạy trong O(log n). Nếu mỗi lời gọi tạo hai lời gọi con, số nút có thể tăng theo tầng. Ngược lại, lũy thừa nhanh ở Bài 7 chỉ cần tính một kết quả nửa số mũ rồi dùng lại; xem Bài 7 để học phép tính modulo.

Chương trình sau đếm số đoạn của mỗi tầng khi chia tám phần tử:

segments = [8]
while segments:
    print(len(segments), sum(segments))
    nxt = []
    for size in segments:
        if size > 1:
            nxt.extend([size // 2, size - size // 2])
    segments = nxt

1 8
2 8
4 8
8 8

Số đoạn tăng nhưng tổng độ dài không đổi ở ví dụ này. Để ước lượng một thuật toán khác, bạn cần đếm việc làm tại từng nút, không chỉ nhìn độ sâu.

Quay lui (backtracking) thử lựa chọn rồi hoàn tác để khám phá phương án. Quy hoạch động (dynamic programming) thường lưu kết quả của các bài toán con lặp lại. Hai nửa của sắp xếp trộn là các đoạn khác nhau, nên không cần lưu để tránh tính lại cùng đoạn. Bài 24 trình bày quay lui; Bài 28 sẽ phát triển quy hoạch động.

Lỗi thường gặp

Tóm tắt

• Đặt trường hợp dừng, chia thành các bài toán nhỏ hơn, rồi chứng minh cách ghép.
• Đoạn [left, right) có độ dài right - left và chia không trùng tại mid.
• Hai dãy tăng trộn trong thời gian tuyến tính; sắp xếp trộn đạt O(n log n).
• Khi phần tử phải nhỏ hơn đầu trái, nó tạo nghịch thế với mọi phần tử trái còn lại.
• Đoạn con lớn nhất nằm trong một nửa hoặc ghép hậu tố trái với tiền tố phải.

Kiểm tra nhanh

Đọc thêm

• Python: sắp xếp danh sách và tính ổn định.
• MIT OpenCourseWare: Merge Sort.