Sắp xếp theo xô¶
Các thuật toán sắp xếp được thảo luận trước đó đều là các thuật toán sắp xếp dựa trên so sánh, vốn sắp xếp bằng cách so sánh thứ tự tương đối của các phần tử. Độ phức tạp thời gian của các thuật toán này không thể vượt qua mức \(O(n \log n)\). Tiếp theo, chúng ta sẽ khám phá một số thuật toán sắp xếp không dựa trên so sánh, có độ phức tạp thời gian có thể đạt mức tuyến tính.
Sắp xếp theo xô là một ứng dụng điển hình của chiến lược chia để trị. Thuật toán hoạt động bằng cách tạo ra một chuỗi các xô được sắp xếp theo thứ tự, mỗi xô tương ứng với một khoảng dữ liệu, và phân phối dữ liệu đồng đều vào các xô đó. Tiếp theo, các phần tử trong mỗi xô sẽ được sắp xếp riêng biệt. Cuối cùng, tất cả các xô được gộp lại theo thứ tự.
Quy trình thuật toán¶
Xét một mảng có độ dài \(n\), với các phần tử là số thực dấu phẩy động trong khoảng \([0, 1)\). Quy trình của sắp xếp theo xô được thể hiện trong hình dưới đây.
- Khởi tạo \(k\) xô và phân phối \(n\) phần tử vào \(k\) xô.
- Sắp xếp riêng biệt từng xô (ở đây chúng ta sử dụng hàm sắp xếp tích hợp sẵn của ngôn ngữ lập trình).
- Gộp các kết quả theo thứ tự từ xô nhỏ nhất đến xô lớn nhất.
Mã nguồn như sau:
Đặc điểm của thuật toán¶
Sắp xếp theo xô phù hợp để xử lý các tập dữ liệu cực kỳ lớn. Ví dụ: giả sử dữ liệu đầu vào chứa 1 triệu phần tử và bộ nhớ hạn chế khiến hệ thống không thể tải tất cả chúng cùng một lúc. Trong trường hợp đó, dữ liệu có thể được chia thành 1000 xô, mỗi xô được sắp xếp riêng biệt và sau đó gộp các kết quả lại.
- Độ phức tạp thời gian là \(O(n + k)\): Giả sử các phần tử được phân phối đều vào các xô, mỗi xô sẽ chứa \(\frac{n}{k}\) phần tử. Nếu sắp xếp một xô đơn lẻ mất thời gian \(O(\frac{n}{k} \log\frac{n}{k})\), thì sắp xếp tất cả các xô sẽ mất thời gian \(O(n \log\frac{n}{k})\). Khi số lượng xô \(k\) tương đối lớn, độ phức tạp thời gian sẽ tiệm cận \(O(n)\). Việc gộp các kết quả yêu cầu duyệt qua tất cả các xô và phần tử, mất thời gian \(O(n + k)\). Trong trường hợp xấu nhất, tất cả dữ liệu được đưa vào cùng một xô và việc sắp xếp xô đó sẽ mất thời gian \(O(n^2)\).
- Độ phức tạp không gian là \(O(n + k)\), không phải sắp xếp tại chỗ: Thuật toán yêu cầu thêm không gian cho \(k\) xô và tổng cộng \(n\) phần tử.
- Việc sắp xếp theo xô có ổn định hay không phụ thuộc vào việc thuật toán sắp xếp các phần tử bên trong từng xô có ổn định hay không.
Cách đạt được phân phối đều¶
Trên lý thuyết, sắp xếp theo xô có thể đạt được độ phức tạp thời gian là \(O(n)\). Chìa khóa ở đây là phân phối các phần tử đều vào các xô, bởi vì dữ liệu thực tế thường không được phân phối đồng đều. Ví dụ, giả sử chúng ta muốn chia đều tất cả các sản phẩm trên Taobao thành 10 xô theo khoảng giá, nhưng sự phân phối giá lại không đồng đều: có rất nhiều sản phẩm có giá dưới 100 nhân dân tệ và rất ít sản phẩm có giá trên 1000 nhân dân tệ. Nếu chia đều khoảng giá thành 10 khoảng bằng nhau, số lượng sản phẩm trong mỗi xô sẽ chênh lệch rất lớn.
Để đạt được phân phối đều hơn, trước tiên chúng ta có thể chọn một ranh giới thô và chia dữ liệu thành 3 xô. Sau đó, các xô chứa nhiều sản phẩm hơn có thể được chia tiếp thành 3 xô nhỏ hơn cho đến khi số lượng phần tử trong tất cả các xô xấp xỉ bằng nhau.
Như được hiển thị trong hình dưới đây, phương pháp này thực chất là xây dựng một cây đệ quy với mục tiêu là làm cho các nút lá cân bằng nhất có thể. Tất nhiên, dữ liệu không nhất thiết phải chia thành 3 xô trong mỗi vòng; chiến lược phân chia cụ thể có thể được lựa chọn linh hoạt dựa trên đặc điểm của dữ liệu.
Nếu chúng ta biết trước phân phối xác suất của giá sản phẩm, chúng ta có thể thiết lập các ranh giới giá cho mỗi xô theo phân phối đó. Đáng chú ý là phân phối dữ liệu không cần phải được đo lường chính xác; nó cũng có thể được xấp xỉ bằng một mô hình xác suất được chọn phù hợp với các đặc tính của dữ liệu.
Như hiển thị trong hình dưới đây, chúng ta giả định rằng giá sản phẩm tuân theo phân phối chuẩn, điều này cho phép chúng ta thiết lập các khoảng giá một cách hợp lý để phân phối đều các sản phẩm vào từng xô.
