Chuyển đến nội dung
MINH VO Ghi chép từ công việc
của một kỹ sư tại Việt Nam
Cơ bản10 phút đọc

Khi tính ổn định của merge sort làm thay đổi kết quả

Theo dõi thứ tự đăng ký khi điểm số bằng nhau, chứng minh merge sort ổn định và kiểm tra cách phối hợp nhiều khóa cùng chiều sắp xếp.

Đồ thị vẽ bằng bút chì trên giấy màu be, với các đường màu ô liu nối những đỉnh

Một phép sắp xếp ổn định giữ nguyên thứ tự đầu vào của các bản ghi có khóa bằng nhau. Nếu danh sách học sinh vốn theo thứ tự đăng ký, sắp xếp ổn định theo điểm sẽ giữ người đăng ký trước ở phía trước trong mỗi nhóm cùng điểm. Với lập trình viên xây dựng bảng xếp hạng hoặc danh sách phân nhóm, khác biệt này hiển thị ngay cho người dùng, dù kết quả ổn định và không ổn định đều có thể thỏa mãn thứ tự số học.

Xét bốn bản ghi theo thứ tự đăng ký: Ava đạt 91, Ben đạt 88, Chi đạt 91 và Dia đạt 88. Nếu yêu cầu ổn định, sắp xếp điểm tăng dần phải cho Ben, Dia, Ava, Chi. Hai cặp đồng điểm giữ Ben trước Dia và Ava trước Chi. Sắp xếp tên theo bảng chữ cái trong từng nhóm điểm là một yêu cầu khác; tính ổn định tự nó không bổ sung quy tắc đó.

Phép trộn quyết định bản ghi nào thắng khi bằng điểm

Merge sort chia đầu vào thành hai nửa, sắp xếp từng nửa rồi trộn hai kết quả. Tính ổn định đòi hỏi mỗi nửa đã ổn định và bước trộn chọn bản ghi bên trái khi khóa bằng nhau. Mọi bản ghi ở nửa trái vốn đều đứng trước mọi bản ghi ở nửa phải.

def stable_score_sort(records):
    if len(records) < 2:
        return list(records)
    middle = len(records) // 2
    left = stable_score_sort(records[:middle])
    right = stable_score_sort(records[middle:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i][0] <= right[j][0]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

students = [(91, 'Ava'), (88, 'Ben'), (91, 'Chi'), (88, 'Dia')]
assert stable_score_sort(students) == [
    (88, 'Ben'), (88, 'Dia'), (91, 'Ava'), (91, 'Chi'),
]

Phép so sánh chỉ dùng điểm ở vị trí số không của tuple. So sánh cả tuple sẽ dùng tên để phân xử khi bằng điểm, tức thực hiện một thứ tự khác. Chẳng hạn, nếu Zoe đăng ký trước Amy và cả hai cùng điểm, hợp đồng này phải giữ Zoe trước Amy dù thứ tự chữ cái sẽ đảo họ lại.

Ở bước trộn cuối trong ví dụ, nửa trái là Ben rồi Ava, nửa phải là Dia rồi Chi. Ben và Dia cùng điểm nên Ben được lấy trước. Sau đó Dia có điểm thấp hơn Ava. Ava và Chi lại cùng điểm nên Ava thắng lần so sánh đó. Kết quả thỏa cả thứ tự điểm lẫn thứ tự ban đầu trong mỗi nhóm đồng điểm.

Trộn ổn định nửa trái Ben tám mươi tám rồi Ava chín mươi mốt với nửa phải Dia tám mươi tám rồi Chi chín mươi mốt, tạo thứ tự Ben Dia Ava ChiMở ảnh kích thước đầy đủ ↗

Đổi <= thành < khiến bước trộn chọn bản ghi bên phải khi bằng điểm. Điểm vẫn không giảm, nên kiểm thử chỉ xét cột điểm sẽ không phát hiện lỗi. Danh tính của bản ghi mới cho thấy tính ổn định đã bị phá vỡ.

Chứng minh thứ tự và tính ổn định riêng biệt

Lập luận thông thường của phép trộn chứng minh thứ tự: phần tử tiếp theo là khóa nhỏ nhất còn lại ở đầu một trong hai nửa. Nó cũng chứng minh mỗi bản ghi đầu vào xuất hiện đúng một lần. Từng tính chất đó, xét riêng, chưa chứng minh tính ổn định.

Với hai bản ghi cùng khóa vốn thuộc một nửa, bảo đảm ổn định của lời gọi đệ quy giữ nguyên thứ tự của chúng. Với hai bản ghi thuộc hai nửa khác nhau, bản ghi bên trái vốn xuất hiện trước. Chọn bên trái mỗi khi bằng khóa giữ quan hệ đó qua ranh giới hai nửa. Hai trường hợp bao phủ mọi cặp khóa bằng nhau, tạo thành chứng minh quy nạp về tính ổn định.

Trường hợp cơ sở trả về bản sao của dãy không có hoặc có một bản ghi, nơi không có cặp nào để đảo thứ tự. Vì trả về bản sao, hàm không sửa danh sách của bên gọi. Tuy nhiên, các đối tượng bản ghi bên trong vẫn là tham chiếu dùng chung; ví dụ không sao chép sâu nội dung của chúng.

Tính cả bộ nhớ tạm

Với n bản ghi, cách chia cân bằng tạo O(log n) tầng đệ quy. Tổng công việc trộn trên mỗi tầng là O(n). Thời gian vì vậy là O(n log n), giả sử so sánh điểm và di chuyển tham chiếu có chi phí hằng số. Chương merge sort của Princeton trình bày phân tích chia để trị này.

Cách cài đặt Python đơn giản tạo các lát cắt và danh sách kết quả. Bộ nhớ bổ sung cực đại là O(n), cộng O(log n) khung ngăn xếp; tổng dung lượng cấp phát qua cả lần chạy lớn hơn vì nhiều tầng cùng tạo các danh sách tạm vào những thời điểm khác nhau. Merge sort dùng cho mảng trong thực tế thường tái sử dụng một vùng đệm để giảm số lần cấp phát. Cả hai cách đều không phải phép sắp xếp tại chỗ với bộ nhớ bổ sung hằng số.

Kết quả ổn định cũng cần khóa nhất quán. Điểm NaN, điểm thay đổi trong lúc sắp xếp hoặc bộ so sánh tự mâu thuẫn đều cần chính sách rõ ràng. Tính ổn định không thể sửa một quan hệ thứ tự vốn không có ý nghĩa nhất quán.

Dùng tính ổn định để phối hợp nhiều khóa

Giả sử kết quả phải ưu tiên điểm, sau đó đến thời gian đăng ký. Khóa ghép (score, registration_time) mô tả trực tiếp yêu cầu này. Một cách khác là sắp xếp theo thời gian đăng ký trước, rồi sắp xếp ổn định theo điểm. Bước sau giữ thứ tự đã thiết lập ở bước trước trong các nhóm đồng điểm. Hướng dẫn sắp xếp của Python mô tả cách làm và bảo đảm ổn định đó.

Thứ tự thực hiện các lượt rất quan trọng. Sắp xếp theo điểm rồi ổn định theo thời gian đăng ký sẽ biến thời gian đăng ký thành khóa chính. Thuật toán ổn định chỉ giữ các quyết định trước ở nơi khóa của lượt sau bằng nhau; nó không khiến các lượt sắp xếp có thể đổi chỗ tùy ý.

Khi kiểm thử, gắn số thứ tự đăng ký vào mỗi bản ghi và xác nhận rằng các số tăng trong từng nhóm cùng điểm. Cần có cặp cùng điểm nằm hai bên điểm chia đệ quy, nhóm toàn cùng điểm và các tên có thứ tự chữ cái ngược thứ tự đăng ký. Những đầu vào này phân biệt hành vi đã hứa với một cột điểm tình cờ có thứ tự.

Theo dõi hai lượt ổn định và phép đảo dễ gây nhầm

Một trường hợp bốn bản ghi giúp nhìn rõ quy tắc nhiều khóa. Mỗi bản ghi chứa điểm, số thứ tự đăng ký và tên. Số thứ tự là khóa phụ tường minh, không còn phụ thuộc vào thứ tự tình cờ cơ sở dữ liệu trả về. Trong ví dụ giả định này, số nhỏ hơn có nghĩa là đăng ký sớm hơn.

records = [
    (91, 30, 'Ava'), (88, 20, 'Ben'),
    (91, 10, 'Chi'), (88, 40, 'Dia'),
]
by_registration = sorted(records, key=lambda row: row[1])
ascending = sorted(by_registration, key=lambda row: row[0])
assert [row[2] for row in by_registration] == ['Chi', 'Ben', 'Ava', 'Dia']
assert [row[2] for row in ascending] == ['Ben', 'Dia', 'Chi', 'Ava']
assert ascending == sorted(records, key=lambda row: (row[0], row[1]))

wrong_pass_order = sorted(
    sorted(records, key=lambda row: row[0]), key=lambda row: row[1],
)
assert [row[0] for row in wrong_pass_order] == [91, 88, 91, 88]

highest_first = sorted(by_registration, key=lambda row: row[0], reverse=True)
assert [row[2] for row in highest_first] == ['Chi', 'Ava', 'Ben', 'Dia']
assert [row[2] for row in reversed(ascending)] == ['Ava', 'Chi', 'Dia', 'Ben']

Sau lượt theo đăng ký, Chi đứng trước Ava và Ben đứng trước Dia. Lượt theo điểm đưa các nhóm điểm vào thứ tự tăng dần, đồng thời giữ các quan hệ đó trong từng nhóm. Làm ngược thứ tự hai lượt khiến đăng ký trở thành khóa chính cuối cùng, nên các điểm có thể xen kẽ tăng giảm. Tính ổn định chỉ hứa giữ thứ tự giữa các bản ghi bằng nhau theo khóa của lượt hiện tại.

Lượt theo đăng ký cho Chi Ben Ava Dia, lượt ổn định theo điểm cho Ben Dia Chi Ava; giảm dần theo điểm vẫn giữ Chi trước Ava và Ben trước Dia, còn đảo cả danh sách làm đảo các cặp đồng điểmMở ảnh kích thước đầy đủ ↗

Điểm giảm dần nhưng đăng ký tăng dần là một hợp đồng khác. Phép sắp xếp ổn định với reverse=True của Python giữ thứ tự đăng ký giữa những người bằng điểm, như ghi chú về tính ổn định khi đảo chiều sắp xếp nêu rõ. Đảo toàn bộ danh sách đã sắp xếp tăng dần sẽ đảo cả từng nhóm đồng điểm. Hai thao tác cho cùng thứ tự của cột điểm nhưng khác thứ tự bản ghi.

Ví dụ dùng thư viện chuẩn để thể hiện ý nghĩa của các lượt, không khẳng định hàm dựng sẵn của Python dùng chính cài đặt merge sort đệ quy ở trên. Hàm trước đó luôn sắp tăng theo trường đầu của tuple. Nếu sửa hàm ấy để điểm giảm dần, hãy vẫn chọn bản ghi trái khi bằng điểm và chỉ đảo chiều so sánh giữa hai điểm khác nhau. Đảo kết quả cuối của nó sẽ mất tính ổn định như ví dụ vừa thấy.

Xác định ý nghĩa của đồng hạng qua nhiều lần tải

Phép sắp xếp ổn định giữ thứ tự đầu vào của lần gọi hiện tại. Nó không tạo ra thứ tự lịch sử nếu hai yêu cầu nhận các hàng đồng điểm theo hai thứ tự khác nhau. Nếu ứng dụng cần bảng xếp hạng lặp lại nhất quán sau mỗi lần tải, hãy đưa số thứ tự đăng ký vào khóa và quy định điều gì xảy ra khi số đó cũng bằng nhau. Mã bản ghi duy nhất có thể làm khóa phân xử cuối nếu đó là quy tắc sản phẩm mong muốn. Bổ sung khóa này thay đổi hợp đồng sắp xếp, nên cần quyết định rõ ràng.

Để luyện tập, cho hai học sinh cùng điểm và cùng số thứ tự đăng ký nhưng khác tên. Khóa ghép chỉ gồm điểm và số thứ tự phải giữ thứ tự đầu vào của họ; thêm tên làm thành phần thứ ba có thể thay đổi kết quả. Sau đó, với điểm dạng số, hãy kiểm tra điểm giảm dần và số thứ tự tăng dần bằng khóa (-score, sequence). Nó phải khớp kết quả hai lượt mà không cần đảo cả danh sách. Những trường hợp này tách rõ tính ổn định, độ ưu tiên giữa các khóa và một khóa phân xử cuối được chỉ định tường minh.

Nguồn tham khảo & đọc thêm

  1. Princeton Algorithms, Mergesort
  2. Python sorting HOWTO, stability and descending order
← Về trang bài viết

Hình minh họa

100%