Phân hoạch quicksort khi có nhiều giá trị trùng
Theo dõi bốn vùng của phân hoạch ba phía, kiểm tra giá trị trùng pivot và giới hạn số khung đệ quy bằng cách chỉ gọi vùng nhỏ hơn.
Quicksort ba phía tách các giá trị nhỏ hơn pivot, bằng pivot và lớn hơn pivot thành ba vùng riêng. Vùng bằng pivot đã hoàn tất, không cần được sắp xếp đệ quy nữa. Nếu đã học quicksort thông thường, bạn có thể dùng một danh sách chứa nhiều giá trị trùng để thấy vì sao vùng bổ sung này làm thay đổi đáng kể lượng công việc.
Phép so sánh cần chỉ rõ sơ đồ phân hoạch hai phía nào đang xét. Một bản kiểu Lomuto chỉ chuyển các giá trị nhỏ hơn hẳn pivot ở cuối sẽ tạo phía nhỏ hơn rỗng trên đầu vào toàn giá trị bằng nhau, rồi đệ quy vào n - 1 giá trị còn lại. Phiên bản đó làm lượng công việc bậc hai. Những sơ đồ hai phía khác, trong đó có phân hoạch Hoare được cài đặt cẩn thận, hành xử khác trên các giá trị bằng nhau; nói mọi quicksort hai phía đều bậc hai khi có khóa trùng là quá rộng.
Duy trì bốn vùng trong lúc quét
Dùng các chỉ số lt, i và gt, khởi đầu lần lượt là không, không và độ dài mảng. Trước mỗi lượt, [0, lt) chứa các giá trị nhỏ hơn pivot, [lt, i) chứa giá trị bằng pivot, [i, gt) chưa được phân loại và [gt, n) chứa giá trị lớn hơn pivot.
def partition_three_way(values, pivot):
lt = i = 0
gt = len(values)
while i < gt:
if values[i] < pivot:
values[lt], values[i] = values[i], values[lt]
lt += 1
i += 1
elif values[i] > pivot:
gt -= 1
values[i], values[gt] = values[gt], values[i]
else:
i += 1
return lt, gt
values = [4, 2, 4, 5, 4, 1]
lo_equal, hi_equal = partition_three_way(values, 4)
assert values == [2, 1, 4, 4, 4, 5]
assert (lo_equal, hi_equal) == (2, 5)Nếu giá trị hiện tại nhỏ hơn pivot, đổi chỗ nó với giá trị bằng pivot đầu tiên rồi tăng cả hai biên trái. Khi lt == i, đó chỉ là đổi một ô với chính nó. Nếu giá trị hiện tại bằng pivot, tăng i để mở rộng vùng bằng.
Nếu giá trị lớn hơn pivot, giảm gt rồi đổi nó với ô chưa phân loại cuối cùng. Chưa được tăng i: giá trị vừa mang từ bên phải về vẫn chưa được phân loại. Bỏ qua bước kiểm tra lại này là lỗi thường gặp, vì nó có thể để một giá trị nhỏ nằm trong vùng được cho là bằng pivot.
Trong ví dụ, số bốn đầu tiên mở rộng vùng bằng. Số hai sau đó đổi lên đầu, và số bốn tiếp theo gia nhập vùng bằng. Số năm đổi chỗ với giá trị chưa phân loại cuối cùng là một. Vì i chưa tăng, một được xét ngay sau đó và chuyển vào vùng nhỏ hơn. Số bốn còn lại hoàn tất lượt quét.
Phân hoạch chưa sắp xếp bên trong từng vùng
Vùng nhỏ hơn trong kết quả là [2, 1], chưa có thứ tự. Cam kết của phân hoạch chỉ nói về quan hệ với pivot, không nói về thứ tự nội bộ của hai vùng ngoài. Quicksort đầy đủ sắp xếp đệ quy [0, lt) và [gt, n), đồng thời bỏ qua [lt, gt).
Mỗi lượt làm giảm gt - i, số giá trị chưa phân loại, đúng một. Vì vậy, phân hoạch toàn mảng này chạy đúng n lượt, dù một lượt có thể dùng một hoặc hai phép so sánh khóa. Nó dùng bộ nhớ bổ sung hằng số và hoán đổi ngay trong mảng.
Khi i == gt, bất biến các vùng chứng minh kết quả: vùng chưa phân loại đã rỗng nên mọi giá trị thuộc đúng vùng theo quan hệ với pivot. Phép đổi chỗ bảo toàn mọi lần xuất hiện của giá trị, kể cả giá trị trùng. Không cần đếm riêng hoặc sao chép riêng các phần tử bằng pivot.
Với mảng toàn giá trị bằng nhau, một lần phân hoạch phân loại hết mọi phần tử và hai vùng ngoài đều rỗng. Công việc của trường hợp này là tuyến tính. Tài liệu quicksort của Princeton và cài đặt ba phía mô tả cách xử lý khóa trùng này.
Cách chọn pivot vẫn ảnh hưởng khi các giá trị khác nhau
Giới hạn còn lại nằm ở việc chọn pivot. Nếu mọi giá trị đều phân biệt và thuật toán tất định liên tục chọn giá trị nhỏ nhất còn lại, phân hoạch ba phía tạo vùng bằng có một phần tử và vùng còn lại có n - 1 phần tử. Tổng công việc vẫn có thể là Θ(n²). Tách khóa bằng nhau giải quyết việc đệ quy lặp lại trên khóa trùng; nó không bảo đảm các vùng cân bằng trên mọi đầu vào.
Chọn pivot ngẫu nhiên hoặc xáo trộn đầu vào cho phép phân tích kỳ vọng O(n log n) theo mô hình ngẫu nhiên tương ứng. Một chính sách chọn pivot tất định có bảo đảm riêng hoặc cơ chế chuyển sang thuật toán dự phòng sẽ đưa ra cam kết khác. Cần nói rõ chính sách đã cài đặt trước khi nêu cận trung bình hay cận xấu nhất.
Trong bản đệ quy đơn giản, ngăn xếp cũng có thể tăng tuyến tính nếu các lần chia rất lệch. Chỉ đệ quy vào vùng nhỏ hơn và xử lý vùng lớn hơn bằng vòng lặp sẽ giới hạn số lời gọi đang hoạt động ở O(log n), dù tổng số phép so sánh vẫn có thể bậc hai. Cần đánh giá thời gian và ngăn xếp riêng.
Kiểm tra các vùng và sự bảo toàn giá trị
So mảng sau phân hoạch với mảng đã sắp xếp hoàn toàn là đòi hỏi nhiều hơn cam kết của hàm. Thay vào đó, xác nhận mọi giá trị trước lt đều nhỏ hơn pivot, từ lt đến trước gt đều bằng pivot, và phần sau đều lớn hơn. Cũng cần đối chiếu tần suất giá trị trước và sau để bắt lỗi làm mất hoặc nhân đôi phần tử.
Hãy thử mảng rỗng, toàn giá trị bằng nhau, pivot không xuất hiện trong mảng và đầu vào xen kẽ nhỏ lớn. Hàm phân hoạch độc lập hỗ trợ pivot vắng mặt bằng cách trả về vùng bằng rỗng, dù quicksort đầy đủ thường chọn pivot trong chính vùng đang xét. Với bản ghi có khóa bằng nhau, sơ đồ hoán đổi này không ổn định; hãy dùng phép sắp xếp ổn định nếu thứ tự ban đầu của chúng là một phần yêu cầu đầu ra.
Giới hạn ngăn xếp mà giữ nguyên công việc phân hoạch
Một cài đặt đầy đủ có thể dùng các khoảng nửa mở trên cùng danh sách và chỉ gọi đệ quy vào vùng ngoài nhỏ hơn. Vùng lớn hơn được xử lý bằng cách cập nhật biên của vòng lặp hiện tại. Phân hoạch vẫn xét mọi giá trị trong vùng; thay đổi cách lên lịch này giới hạn số lời gọi đồng thời, không làm giảm số phép so sánh của một chuỗi pivot xấu.
Hàm dưới đây trả về số lời gọi sắp xếp cùng hoạt động lớn nhất để kiểm tra lập luận về bộ nhớ. Đầu vào rỗng hoặc có một phần tử không cần lời gọi sắp xếp nào và trả về không. Giá trị trả về là số khung, không phải số byte hay tổng số lần gọi đệ quy. Danh sách đầu vào chứa kết quả đã sắp xếp.
def quicksort_three_way(values):
peak = 0
def sort_range(lo, hi, depth):
nonlocal peak
peak = max(peak, depth)
while hi - lo > 1:
pivot = values[lo]
lt = i = lo
gt = hi
while i < gt:
if values[i] < pivot:
values[lt], values[i] = values[i], values[lt]
lt += 1
i += 1
elif values[i] > pivot:
gt -= 1
values[i], values[gt] = values[gt], values[i]
else:
i += 1
if lt - lo < hi - gt:
if lt - lo > 1:
sort_range(lo, lt, depth + 1)
lo = gt
else:
if hi - gt > 1:
sort_range(gt, hi, depth + 1)
hi = lt
if len(values) > 1:
sort_range(0, len(values), 1)
return peak
repeated = [4] * 16
assert quicksort_three_way(repeated) == 1
mixed = [4, 2, 4, 5, 4, 1]
quicksort_three_way(mixed)
assert mixed == [1, 2, 4, 4, 4, 5]
assert quicksort_three_way([]) == 0Pivot ở đây nằm trong vùng đang xét, nên vùng bằng chứa ít nhất một giá trị. Với vùng dài m, tổng kích thước hai vùng ngoài nhiều nhất là m - 1. Vùng nhỏ hơn có nhiều nhất floor((m - 1) / 2) giá trị. Mỗi khung đệ quy mới đi vào vùng nhỏ hơn đó, nên việc liên tục thêm khung làm kích thước giảm ít nhất một nửa ở mỗi bước. Số khung sắp xếp cực đại do đó là O(log n), dù một khung có thể xử lý nhiều vùng lớn hơn qua vòng lặp.
Chuỗi pivot cực trị trong hình là ví dụ chi phí có điều kiện, không khẳng định mọi đầu vào đã sắp xếp đều theo đúng dấu vết đó trong cài đặt có hoán đổi này. Nếu mỗi pivot là giá trị phân biệt nhỏ nhất còn lại, các vùng giảm từ mười sáu xuống mười lăm rồi tiếp tục đến hai. Tổng số lượt phân hoạch là 16 + 15 + ... + 2 = 135, nhưng chỉ có một khung sắp xếp đang hoạt động: phía nhỏ hơn rỗng không bao giờ được gọi đệ quy. Với mười sáu giá trị bằng nhau, lần phân hoạch đầu thực hiện mười sáu lượt và hoàn tất trong một khung. Cùng đỉnh ngăn xếp có thể che giấu lượng công việc rất khác nhau.
Cài đặt đầy đủ không tạo lát cắt. Việc hoán đổi dùng trạng thái làm việc hằng số trên mỗi khung, nhưng đệ quy thêm O(log n) trạng thái phụ, nên gọi cả phép sắp xếp là bộ nhớ hằng số sẽ không chính xác. Nó vẫn không ổn định, giả sử so sánh nhất quán và dùng giá trị đầu vùng làm pivot tất định. Riêng cải thiện ngăn xếp không cung cấp cam kết về thời gian kỳ vọng.
Nếu bổ sung hàm lấy khóa, hãy mở rộng kiểm thử bằng bản ghi cùng khóa có nhãn. Cũng nên liệt kê các mảng số nguyên ngắn trên một tập giá trị nhỏ. Kiểm tra riêng kết quả có thứ tự, số lần xuất hiện được bảo toàn và đỉnh ngăn xếp được báo cáo. Với n >= 2, floor(log2(n)) là cận trên an toàn cho số khung sắp xếp hoạt động của cài đặt này. Kiểm thử cận đó không chứng minh thời gian chạy nhanh; nếu thêm bộ đếm công việc phân hoạch, hãy giữ nó tách biệt.