Tổng quan
Quicksort Ba Chiều là quicksort thường với một phép phân hoạch khôn hơn. Thay vì chia mảng thành 'nhỏ hơn chốt' và 'không nhỏ hơn chốt', nó chia thành ba vùng chỉ trong một lượt quét: nhỏ hơn chốt, bằng chốt, và lớn hơn chốt.
Vùng ở giữa mới là điểm mấu chốt. Khi một loạt khóa bằng nhau rơi vào đó, chúng đã nằm đúng vị trí cuối cùng và không bao giờ bị đụng tới nữa, nên một mảng chỉ có vài giá trị phân biệt được sắp gần như tuyến tính — đúng cái đầu vào khiến quicksort thường tụt xuống O(n²). Phép phân hoạch này là bài toán 'quốc kỳ Hà Lan' của Dijkstra, gọi theo ba dải màu mà nó tạo ra.
Quicksort Ba Chiều hoạt động thế nào?
- Chọn một chốt, rồi giữ ba chỉ số di động: lt đánh dấu cuối vùng 'nhỏ hơn', gt đánh dấu đầu vùng 'lớn hơn', và i là phần tử đang xét.
- Nếu phần tử hiện tại nhỏ hơn chốt, đổi nó vào ranh giới lt rồi tăng cả lt lẫn i.
- Nếu nó lớn hơn chốt, đổi xuống ranh giới gt rồi dịch gt sang trái — nhưng KHÔNG tăng i, vì giá trị vừa đổi vào chưa được xét.
- Nếu nó bằng chốt, cứ để yên và chỉ tăng i; nó đã nằm trong dải giữa rồi.
- Dừng khi i vượt qua gt, rồi chỉ đệ quy trên hai vùng ngoài. Mọi phần tử bằng chốt đã xong.
Khi nào nên dùng?
- Bất kỳ tập dữ liệu nào trùng lặp nhiều: cờ trạng thái, danh mục, xếp hạng, các cột kiểu đúng/sai, hay mốc thời gian đã làm tròn theo ngày.
- Sắp theo một khóa ít giá trị phân biệt trước khi gom nhóm — dải bằng nhau cho bạn sẵn các nhóm.
- Làm sort tại chỗ mặc định trong các thư viện không thể giả định gì về phân bố đầu vào.
- Không đáng thêm nhánh khi các khóa gần như phân biệt hết — quicksort thường làm ít việc hơn trên mỗi phần tử trong trường hợp đó.
Phân tích độ phức tạp
Thời gian trung bình vẫn là O(n log n), giống quicksort chuẩn. Lợi ích lộ ra ở hai thái cực: khi chỉ có vài khóa phân biệt, mỗi lần phân hoạch hoàn tất vĩnh viễn một khối lớn và tổng thể tụt về gần O(n). Trường hợp xấu nhất O(n²) vẫn tồn tại trên lý thuyết — một dãy chốt bất lợi trên các khóa phân biệt — nên các cài đặt thực tế đều chọn chốt ngẫu nhiên hoặc trung vị của ba. Bộ nhớ là O(log n) cho ngăn xếp đệ quy, vì bản thân phép phân hoạch làm tại chỗ.
Câu hỏi thường gặp
Vì sao quicksort thường lại chật vật với phần tử trùng lặp?
Phân hoạch hai chiều buộc phải đẩy mọi khóa bằng chốt về một trong hai phía. Mảng mà mọi khóa giống nhau vì thế chia thành một phần rỗng và một phần cỡ n − 1, đúng hình dạng O(n²). Cách ba chiều loại hẳn các khóa đó khỏi bài toán.
Nó có ổn định không?
Không. Phép phân hoạch hoán đổi các phần tử ở khoảng cách xa, nên hai bản ghi cùng khóa có thể ra theo thứ tự tương đối khác lúc vào. Nếu cần ổn định, merge sort là câu trả lời quen thuộc.
Cách này khác gì counting sort trên dữ liệu ít giá trị phân biệt?
Counting sort cần biết trước khoảng giá trị của khóa và cấp phát một thùng cho mỗi khóa khả dĩ, chỉ dùng được với khóa kiểu số nguyên nhỏ. Quicksort ba chiều không giả định gì về khóa ngoài việc so sánh được, và sắp xếp tại chỗ.