Sắp xếp không so sánh, và khi nào O(n) được phép
Sắp xếp không so sánh, và khi nào O(n) được phép
Bài trước chứng minh không thuật toán sắp xếp nào rẻ hơn log₂(n!) phép so sánh. Hai thuật toán trong bài này chạy O(n + k) và tiêu 0 phép so sánh. Cả hai câu đều đúng, và chỗ chúng gặp nhau là bài học.
Ở bài sắp xếp trộn bạn đã gặp một chứng minh khó chịu. Một thuật toán chỉ được phép hỏi a có nhỏ hơn b không thì mỗi câu hỏi cho 2 nhánh trả lời, nên sau k câu nó phân biệt được nhiều nhất 2ᵏ khả năng. Số thứ tự có thể của n phần tử là n!. Muốn phân biệt hết thì 2ᵏ ≥ n!, tức k ≥ log₂(n!). Với 20 phần tử con số đó là 61,0774, làm tròn lên là 62 phép so sánh, và không cách viết mã nào lách được.
Bài này giới thiệu hai thuật toán tiêu đúng 0 phép so sánh trên đúng 20 phần tử ấy.
Đừng vội nghĩ có ai sai. Câu chứng minh ở trên có một mệnh đề điều kiện mà người ta hay đọc lướt: nó nói về thuật toán dựa trên so sánh, tức lớp thuật toán mà thao tác duy nhất được phép làm với dữ liệu là đem hai phần tử ra so. Hai thuật toán dưới đây không thuộc lớp đó. Chúng không so sánh gì cả, chúng lấy giá trị của phần tử làm địa chỉ ô nhớ. Đó là một quyền lực khác hẳn, và như mọi quyền lực khác, nó có giá.
Sim dưới đây đếm chính xác cả hai vế: số phép so sánh (luôn 0, và bộ đếm nằm ngay trong vòng lặp chứ không phải một dòng chữ), và cái giá phải trả tính bằng ô nhớ và bằng bước.
1 · Mảng vào và dải giá trị khai báo ✎ sửa được
2 · Không có phép so sánh nào, và chặn dưới
| đại lượng | giá trị | nó nói gì |
|---|---|---|
| so sánh phần tử, sắp xếp đếm | 0 | Đo bằng bộ đếm đặt trong chính vòng lặp, không phải khai báo. |
| so sánh phần tử, theo cơ số | 0 | Nó chạy 2 lượt sắp xếp đếm, mỗi lượt cũng 0. |
| chặn dưới log₂(n!) | 61,0774 | Với n = 20, mọi thuật toán dựa trên so sánh cần ít nhất 62 phép so sánh ở ca xấu nhất. |
3 · Sắp xếp đếm, từng bước
i giờ đọc là có bấy nhiêu phần tử có giá trị nhỏ hơn hoặc bằng 0 + i, tức đúng vị trí kết thúc của nhóm đó trong mảng kết quả.| lượt ghi | đọc ô vào số | giá trị | ô đếm số | ghi vào ô ra số |
|---|---|---|---|---|
| 1 | 19 | 4 | 4 | 8 |
| 2 | 18 | 5 | 5 | 9 |
| 3 | 17 | 1 | 1 | 4 |
| 4 | 16 | 15 | 15 | 19 |
| 5 | 15 | 13 | 13 | 17 |
| 6 | 14 | 9 | 9 | 12 |
| 7 | 13 | 4 | 4 | 7 |
| 8 | 12 | 11 | 11 | 15 |
| 9 | 11 | 2 | 2 | 6 |
| 10 | 10 | 0 | 0 | 3 |
| 11 | 9 | 15 | 15 | 18 |
| 12 | 8 | 2 | 2 | 5 |
| 13 | 7 | 12 | 12 | 16 |
| 14 | 6 | 9 | 9 | 11 |
| 15 | 5 | 7 | 7 | 10 |
| 16 | 4 | 10 | 10 | 14 |
| 17 | 3 | 10 | 10 | 13 |
| 18 | 2 | 0 | 0 | 2 |
| 19 | 1 | 0 | 0 | 1 |
| 20 | 0 | 0 | 0 | 0 |
4 · Hoá đơn, và mốc hoà vốn
| khoản | bằng gì | số bước |
|---|---|---|
| dựng mảng đếm | k = 16 | 16 |
| đếm | n = 20 | 20 |
| cộng dồn | k − 1 = 15 | 15 |
| rải | n = 20 | 20 |
| tổng | 2n + 2k − 1 | 71 |
- Một bước ở đây là một lần chạm vào một ô: đặt một ô đếm về 0, tăng một ô đếm, cộng một lần khi cộng dồn, ghi một phần tử ra.
- Thước
⌈n·log₂n⌉là cỡ của sắp xếp trộn viết trong cùng đơn vị đó. Ghép hai thứ vào một trục là một quy ước, không phải chân lý: sắp xếp trộn còn tốn phép chép và ô nhớ đệm mà thước này không kể. Đổi quy ước thì mọi con số cột này dịch theo cùng một hệ số, còn hình dạng của mốc hoà vốn thì không đổi, và hình dạng đó mới là điều đáng nhớ.
5 · Cái giá thật: mảng đếm dài bằng cả dải
1000000 rồi đọc lại ba con số này.| dải khai báo | k | ô nhớ phụ | bước | lần thước so sánh |
|---|---|---|---|---|
| 0 tới 9 | 10 | 30 | 59 | 0,7 |
| 0 tới 255 | 256 | 276 | 551 | 6,3 |
| 1 tới 1.000 | 1.000 | 1.020 | 2.039 | 23,4 |
| 1 tới 100.000 | 100.000 | 100.020 | 200.039 | 2299,3 |
| 1 tới 1.000.000 | 1.000.000 | 1.000.020 | 2.000.039 | 22989,0 |
6 · Sắp xếp theo cơ số ✎ sửa được
| cơ số | số lượt | ô đếm mỗi lượt | bước mỗi lượt | tổng bước |
|---|---|---|---|---|
| 2 | 4 | 2 | 43 | 172 |
| 10 ← | 2 | 10 | 59 | 118 |
| 16 | 1 | 16 | 71 | 71 |
| 256 | 1 | 256 | 551 | 551 |
| đếm thẳng | 1 | 16 | 71 | 71 |
⌈logb(dải + 1)⌉. Ở đây dải là 15, cơ số 10, nên 2 lượt. Cơ số lớn thì ít lượt hơn nhưng mỗi lượt phải dựng lại mảng đếm to hơn, và hai chiều đó không triệt tiêu nhau gọn ghẽ: trên cấu hình hiện tại, cơ số rẻ nhất là 16. Đổi dải rồi xem con số đó chạy.| lượt | sắp theo hàng | mảng sau lượt đó | đã đúng thứ tự chưa |
|---|---|---|---|
| 1 | 1 | 000101001111222134415155799 | ✗ chưa |
| 2 | 10 | 000012244579910101112131515 | ✓ rồi |
7 · Tính ổn định, chỗ sắp xếp theo cơ số sống hay chết ✎ sửa được
| chạy cái gì | kết quả, đọc từ trái sang | giữ nguyên thứ tự cũ của khoá bằng nhau |
|---|---|---|
| đầu vào | 3A1B3C2D1E | chưa sắp gì cả |
| rải ngược | 1B1E2D3A3C | ✓ có, thứ tự cũ còn nguyên |
| rải xuôi | 1E1B2D3C3A | ✗ không: cùng khoá 1, B vào trước E mà lại ra sau |
| sắp xếp theo cơ số 10 trên dãy 21 12 11 22 | kết quả | đúng thứ tự |
|---|---|---|
| rải ngược, 2 lượt | 11122122 | ✓ đúng |
| rải xuôi, 2 lượt | 12112221 | ✗ SAI, mảng không tăng dần |
- Nó đếm bước và ô nhớ, nó không đo thời gian chạy. Một bước chạm mảng đếm và một bước chạm mảng vào không hề đắt bằng nhau trên máy thật, vì mảng đếm một triệu ô thì không nằm vừa bộ nhớ đệm. Ở chiều đó, sắp xếp đếm còn tệ hơn con số ở đây.
- Quy một bước cho mỗi ô bị chạm, rồi đặt cạnh
⌈n·log₂n⌉của sắp xếp trộn, là một quy ước. Hai vế không cùng đơn vị thật. Mốc hoà vốn vì thế là mốc của mô hình này, không phải một hằng số của tự nhiên. kở đây là dải khai báo. Một bản cài đặt thật thường quét mảng tìm giá trị nhỏ nhất và lớn nhất trước, tốn thêmnbước, rồi dùng dải quan sát được. Sim để bạn tự đặt dải vì đó là cách nhìn rõ nhấtklà cái gì, và vì dữ liệu rải đều thì dải quan sát được cũng gần bằng dải khai báo: hiện tại dải khai báo 16 còn dải quan sát được là 16.- Hai thuật toán này chỉ nhận số nguyên. Giá trị âm được xử lý bằng cách trừ đi đầu dưới của dải trước khi dùng làm chỉ số, nên chúng chạy được, nhưng số thực hay chuỗi thì cần cách khác.
- Dãy ngẫu nhiên sinh bằng bộ sinh giả ngẫu nhiên viết trong engine, không dùng đồng hồ và không dùng
Math.random. Cùng hạt giống thì luôn cùng dãy, trên máy chủ cũng như trên trình duyệt, và cổng kiểm số khoá đúng điều đó.
Trạng thái mở bài đang nói gì
Sim khởi động ở 20 phần tử, dải giá trị khai báo là 0 tới 15, hạt giống 2026, ra mảng 0 0 0 10 10 7 9 12 2 15 0 2 11 4 9 13 15 1 5 4. Trong đó có 12 giá trị khác nhau, giá trị nhỏ nhất 0 và lớn nhất 15.
Dải rộng 16 giá trị nên mảng đếm có 16 ô, và 4 ô trong số đó sẽ không bao giờ khác 0. Cộng 20 ô của mảng kết quả là 36 ô nhớ phụ.
Hoá đơn chia làm bốn khoản, mỗi khoản đếm được riêng:
- dựng mảng đếm: 16 bước, đúng bằng
k, tức đặt từng ô đếm về 0; - đếm: 20 bước, đúng bằng
n, một lượt quét mảng vào; - cộng dồn: 15 bước, đúng bằng
k − 1, số phép cộng trong tổng chạy; - rải: 20 bước, đúng bằng
n, mỗi phần tử ghi ra một lần.
Tổng là 71 bước, tức công thức 2n + 2k − 1. Thước so sánh, lấy cỡ ⌈n·log₂n⌉ của sắp xếp trộn, cho 87. Sắp xếp đếm đang rẻ hơn 16 bước, tỉ lệ 0,82.
Và cột quan trọng nhất: so sánh phần tử = 0. Không phải "ít", không phải "gần như không", mà đúng bằng 0, trong khi chặn dưới cho mọi thuật toán dựa trên so sánh ở n = 20 là 62.
Ba bước của sắp xếp đếm, và vì sao không bước nào so sánh
Bước đếm. Quét mảng vào một lượt. Gặp giá trị v thì tăng ô đếm số v − lo lên 1. Ở đây lo là đầu dưới của dải, và phép trừ đó chính là cách thuật toán nhận cả giá trị âm: dải −3 tới 2 thì giá trị −3 đi vào ô 0. Không có phép so sánh nào vì không cần: giá trị tự nói nó thuộc về ô nào.
Bước cộng dồn. Thay mỗi ô bằng tổng của nó và mọi ô đứng trước. Sau bước này ô thứ i đọc là có bấy nhiêu phần tử mang giá trị nhỏ hơn hoặc bằng lo + i. Ở mảng mở bài, mảng đếm 4 1 2 0 2 1 0 1 0 2 2 1 1 1 0 2 biến thành 4 5 7 7 9 10 10 11 11 13 15 16 17 18 18 20, và số cuối cùng phải bằng đúng n, tức 20. Đây chỉ là phép cộng, cũng không so sánh gì.
Bước rải. Đi ngược từ cuối mảng vào. Mỗi phần tử lấy ô đếm của mình, trừ đi 1, rồi ghi mình vào đúng chỉ số vừa nhận. Ở mảng mở bài, lượt ghi đầu tiên đọc ô vào số 19 và ghi vào ô ra số 8. Vẫn không so sánh.
Vì sao đi ngược, mục Tính ổn định bên dưới trả lời, và nó không phải chi tiết trang trí.
Ba bước cộng lại cho O(n + k). Cái k đó là chỗ toàn bộ câu chuyện nằm, và nó cũng là một ví dụ đẹp cho điều bài bậc tăng đã cảnh báo: một biểu thức O chỉ có nghĩa khi bạn nói rõ các chữ cái trong đó là gì. Ai đọc O(n + k) rồi tự dịch thành "tuyến tính theo số phần tử" là đã bỏ mất đúng một nửa công thức, và nửa bị bỏ mới là nửa đắt.
Cái giá: mảng đếm dài bằng cả dải, không phải bằng dữ liệu
k không phải số giá trị khác nhau trong dữ liệu. Nó là bề rộng của dải khai báo. Ở trạng thái mở bài, dữ liệu có 12 giá trị khác nhau nhưng mảng đếm vẫn 16 ô, vì dải khai báo là 0 tới 15.
Bấm nút 1 tới 1.000.000 ở mục 1 và đọc lại ba con số. Vẫn 20 phần tử, vẫn một dòng số ngắn trên màn hình, nhưng:
| dải khai báo | k | ô nhớ phụ | bước | lần thước so sánh |
|---|---|---|---|---|
| 0 tới 9 | 10 | 30 | 59 | 0,7 |
| 0 tới 255 | 256 | 276 | 551 | 6,3 |
| 1 tới 1.000 | 1.000 | 1.020 | 2.039 | 23,4 |
| 1 tới 100.000 | 100.000 | 100.020 | 200.039 | 2.299,3 |
| 1 tới 1.000.000 | 1.000.000 | 1.000.020 | 2.000.039 | 22.989,0 |
Hàng cuối: sắp xếp 20 con số bằng một triệu lẻ hai mươi ô nhớ và hai triệu lẻ ba mươi chín bước, trong khi thước so sánh vẫn đứng yên ở 87. Chậm hơn 22.989 lần. Trong hai triệu bước ấy, đúng 20 bước dành cho việc nhìn dữ liệu; 1.000.000 bước để đặt mảng đếm về 0 và 999.999 bước để cộng dồn. Và 999.980 ô đếm chưa bao giờ khác 0.
Đây là lý do sim từ chối cấp phát mảng đếm quá 4.096 ô: chi phí vẫn tính ra được vì nó là số học đóng, nhưng chạy thật thì không, và cái trần đó tự nó đã là bài học.
Nói cho sòng phẳng một chỗ: một bản cài đặt thật thường quét mảng tìm giá trị nhỏ nhất và lớn nhất trước, tốn thêm n bước, rồi lấy dải quan sát được thay vì dải khai báo. Sim để bạn tự đặt dải vì đó là cách nhìn rõ nhất k là cái gì. Nhưng với dữ liệu rải đều thì việc quét không cứu được ai: ở hàng cuối bảng trên, 20 giá trị lấy đều trong 1 tới 1.000.000 có giá trị nhỏ nhất 21.250 và lớn nhất 998.167, tức dải quan sát được vẫn rộng 976.918.
Mốc hoà vốn, và cả hai phía của nó
Với n = 20, sắp xếp đếm tốn 2n + 2k − 1 = 39 + 2k bước, còn thước so sánh tốn 87. Giải bất phương trình 39 + 2k > 87 cho k > 24, nên mốc hoà vốn là k = 25.
Cả hai phía của mốc đều kiểm được, và cổng kiểm số khoá đúng hai điểm đó:
k = 24cho39 + 48 = 87bước, bằng đúng thước so sánh, tức chưa thua;k = 25cho39 + 50 = 89bước, đã vượt.
Chỗ dễ nói sai: mốc này không phải hằng số, nó bò theo n. Ở n = 8 mốc là 5 ô đếm, ở n = 100 là 234, ở n = 1000 là 3.984, ở n = 10.000 là 56.440. Tính theo đầu phần tử thì mốc đi từ 2,34 ô ở n = 100 lên 5,64 ô ở n = 10.000, vì n log₂ n mọc nhanh hơn n. Nghĩa là dữ liệu càng lớn, sắp xếp đếm càng có đất, miễn dải giá trị đừng lớn theo.
Và một mốc biên ngược chiều mà công thức tự nói ra: ở n = 2 mốc hoà vốn là 1, tức không có k nào để sắp xếp đếm thắng. Thước so sánh chỉ tiêu 2 bước cho 2 phần tử, còn sắp xếp đếm với đúng một ô đếm đã tiêu 5. Trên dữ liệu tí hon thì cái giá cố định của việc dựng mảng đếm nuốt sạch lợi thế.
Quy một bước cho mỗi ô bị chạm, rồi đặt cạnh ⌈n·log₂n⌉ của sắp xếp trộn, là một quy ước, không phải chân lý: sắp xếp trộn còn tốn phép chép và n ô nhớ đệm mà thước này không kể tới. Đổi quy ước thì mọi con số ở cột đó dịch theo cùng một hệ số, và mốc hoà vốn dịch theo. Cái không đổi là hình dạng: chi phí của sắp xếp đếm tuyến tính theo k, chi phí của thuật toán so sánh không phụ thuộc k chút nào, nên hai đường luôn cắt nhau đúng một lần. Hình dạng đó mới là điều đáng nhớ.
Sắp xếp theo cơ số: đổi một k khổng lồ lấy vài lượt
Sắp xếp theo cơ số giải đúng cái ca vừa làm sập sắp xếp đếm. Thay vì một mảng đếm dài bằng cả dải, nó chạy sắp xếp đếm nhiều lượt, mỗi lượt chỉ nhìn một chữ số của giá trị, từ hàng thấp nhất lên. Mảng đếm mỗi lượt chỉ dài bằng cơ số.
Số lượt bằng số chữ số của giá trị lớn nhất viết trong cơ số đó, tức ⌈log_b(dải + 1)⌉. Ở trạng thái mở bài, dải là 15 và cơ số 10 nên 2 lượt, mỗi lượt tốn 2n + 2b − 1 = 59 bước, tổng 118.
Đổi cơ số thì hai đại lượng chạy ngược chiều nhau, và bảng cho thấy chúng không triệt tiêu gọn ghẽ. Với 20 phần tử, dải 0 tới 15:
| cơ số | số lượt | ô đếm mỗi lượt | tổng bước |
|---|---|---|---|
| 2 | 4 | 2 | 172 |
| 10 | 2 | 10 | 118 |
| 16 | 1 | 16 | 71 |
| 256 | 1 | 256 | 551 |
Cơ số 16 rẻ nhất, và con số 71 của nó không phải trùng hợp: dải rộng đúng 16 nên một lượt là đủ, và một lượt sắp xếp theo cơ số trên 16 ô đếm chính là sắp xếp đếm trên 16 ô đếm, giống nhau từng bước. Cơ số 256 thì thua đậm vì phải dựng lại 256 ô đếm để sắp 20 số.
Bây giờ đổi dải sang 1 tới 1.000.000 rồi đọc lại đúng bảng đó:
| cơ số | số lượt | ô đếm mỗi lượt | tổng bước |
|---|---|---|---|
| 2 | 20 | 2 | 900 |
| 10 | 6 | 10 | 394 |
| 16 | 5 | 16 | 395 |
| 256 | 3 | 256 | 1.693 |
Sắp xếp đếm trên cùng dữ liệu tốn 2.000.039 bước. Sắp xếp theo cơ số 10 tốn 394, tức rẻ hơn 5.076,2 lần, và nó dùng 10 ô đếm thay vì một triệu. Nói gọn: nó biến k thành log_b(k) lượt.
Chú ý cơ số 10 và cơ số 16 chênh nhau đúng 1 bước ở đây (394 với 395), tức kẻ thắng đổi tay theo dải chứ không có cơ số nào tốt nhất tuyệt đối. Đó là lý do bảng đó nằm trong sim để bạn tự chạy, chứ không phải một lời khuyên chép sẵn. Bốn con số trên đều đã cộng thêm 40 bước tiền trừ rồi cộng trả lại đầu dưới của dải: dải bắt đầu ở 1 chứ không phải 0 nên mỗi giá trị phải dời hai lần, tốn 2n bước.
Một chỗ đặc tả của bài này ghi sai và chỉ đo lại mới lòi ra: công thức số lượt không phải ⌈log_b(giá trị lớn nhất)⌉. Công thức đó hỏng ở mọi luỹ thừa đúng của cơ số. Với cơ số 10 và giá trị lớn nhất 1000 nó cho 3 trong khi số chữ số thật là 4, và với giá trị lớn nhất bằng 1 nó cho 0, tức bảo rằng không cần lượt nào. Công thức đúng là ⌈log_b(giá trị lớn nhất + 1)⌉, và engine tính bằng phép chia nguyên lặp lại để khỏi đụng số thực. Cổng kiểm số đối chiếu 20.004 cặp giá trị và cơ số, cộng ba phản ví dụ nêu tên.
Tính ổn định: chỗ sắp xếp theo cơ số sống hay chết
Một thuật toán sắp xếp gọi là ổn định khi hai phần tử có khoá bằng nhau vẫn giữ nguyên thứ tự cũ sau khi sắp. Ở bài ba thuật toán bậc hai tính chất này là một điều tốt nên có. Ở đây nó là điều kiện sống còn, và mục 7 của sim để bạn tự tháo nó ra.
Toàn bộ khác biệt nằm ở chiều của vòng lặp cuối. Rải ngược, tức đi từ cuối mảng vào, thì hai phần tử bằng khoá giữ nguyên thứ tự. Rải xuôi thì chúng bị đảo. Hai cách tiêu đúng bằng nhau số bước, và cả hai đều trả về khoá đúng thứ tự, nên trên một lần sắp xếp đếm khác biệt này gần như vô hình.
Trên danh sách 3A 1B 3C 2D 1E, cũng chính danh sách của bài trước:
- rải ngược ra
1B 1E 2D 3A 3C, đúng như sắp xếp chèn và nổi bọt đã cho ở bài trước; - rải xuôi ra
1E 1B 2D 3C 3A, tức mọi cặp trùng khoá đều đảo.
Cả hai đều tốn 15 bước và cả hai đều xếp đúng theo điểm. Nếu bản ghi chỉ là một con số trần thì bạn không có cách nào phát hiện ra.
Cái giá thật lộ ra khi bạn xâu chuỗi nhiều lượt, và đó chính xác là điều sắp xếp theo cơ số làm. Lấy dãy 21 12 11 22, cơ số 10, hai lượt:
- rải ngược: lượt hàng đơn vị cho
21 11 12 22, lượt hàng chục cho11 12 21 22, đúng thứ tự; - rải xuôi: lượt hàng đơn vị cho
11 21 22 12, lượt hàng chục cho12 11 22 21, không phải một dãy tăng dần.
Đây không phải "thứ tự phụ bị xáo". Đây là kết quả sai. Lý do: lượt hàng chục dựa vào một giả định rằng thứ tự do lượt hàng đơn vị dựng ra vẫn còn nguyên trong nội bộ mỗi nhóm cùng hàng chục. Một lượt không ổn định đảo đúng cái thứ tự đó, tức nó xoá sạch công của lượt trước. Sắp xếp theo cơ số không phải một thuật toán dùng sắp xếp đếm cho tiện; nó là một thuật toán đứng trên tính ổn định, và tháo ra là nó đổ.
Ở trạng thái mở bài, bấm rải xuôi rồi nhìn dòng kết quả cuối của mục 6: 20 số ra 9 9 7 5 4 4 2 2 1 0 0 0 0 15 15 13 12 11 10 10, và sim nói thẳng là không đúng thứ tự.
Một mốc biên phải nói cho đúng, vì nói quá lời ở đây rất dễ. Chọn cơ số 256 thì dãy 21 12 11 22 chỉ cần một lượt, và một lượt thì không có công của ai để mà xoá: rải xuôi vẫn ra 11 12 21 22, đúng thứ tự. Câu đúng là sắp xếp theo cơ số cần tính ổn định từ lượt thứ hai trở đi. Cổng kiểm số khoá đúng hai bên mốc đó: cơ số 256 với 1 lượt thì không vỡ, cơ số 16 với 2 lượt thì vỡ.
Và một chỗ nữa cần nói cho đủ: quét toàn bộ lưới cấu hình, một sắp xếp đếm không ổn định chưa bao giờ trả về mảng số sai thứ tự, còn một sắp xếp theo cơ số không ổn định vỡ ở 144 trên 896 cấu hình. Không ổn định không có nghĩa là luôn hỏng; nó có nghĩa là không có bảo đảm, và ai xây tiếp lên trên nó thì người đó lãnh đủ.
Vậy dùng cái nào
Sắp xếp đếm đáng dùng khi dải giá trị nhỏ và biết trước: điểm thi 0 tới 10, tuổi 0 tới 120, byte 0 tới 255, mã bưu chính trong một tỉnh. Ở những ca đó k nằm sâu dưới mốc hoà vốn và nó thắng bất kỳ thuật toán so sánh nào, đồng thời còn ổn định miễn bạn nhớ rải ngược.
Sắp xếp theo cơ số đáng dùng khi dữ liệu là số nguyên cố định độ dài, dải rộng nhưng số chữ số ít: khoá 32 bit chỉ cần 4 lượt cơ số 256. Nó là thuật toán được dùng thật cho những việc như sắp xếp hàng tỉ khoá số trong cơ sở dữ liệu và trong đồ hoạ.
Cả hai đều không dùng được khi khoá không phải số nguyên, hoặc khi bạn chỉ có một hàm so sánh hai phần tử mà không có cách biến khoá thành chỉ số. Đó là ca phổ biến nhất trong lập trình thường ngày, và đó là lý do thư viện chuẩn của mọi ngôn ngữ vẫn dùng thuật toán so sánh làm mặc định. Chặn dưới log₂(n!) không bị phá; nó chỉ không áp vào đây, và cái giá của việc bước ra ngoài phạm vi của nó đo được bằng ô nhớ.
Vài điểm nhỏ nhưng hay bị bỏ qua:
- Sim đếm bước và ô nhớ, nó không đo thời gian. Một bước chạm mảng đếm một triệu ô và một bước chạm mảng vào 20 ô không hề đắt bằng nhau trên máy thật, vì cái thứ nhất trượt bộ nhớ đệm liên tục. Ở chiều đó sắp xếp đếm còn tệ hơn con số trong bài.
- Giá trị âm được xử lý tường minh, không phải bị từ chối: mọi khoá trừ đi đầu dưới của dải trước khi dùng làm chỉ số, nên dải
−3tới2cho 6 ô đếm và chạy bình thường. Sắp xếp theo cơ số cũng dời như vậy rồi cộng trả lại, và cái dời đó tốn2nbước. - Mảng rỗng vẫn phải trả tiền. Đặt số phần tử về 0 mà giữ dải 0 tới 15: 0 phần tử, nhưng vẫn 31 bước, vì 16 ô đếm phải dựng và 15 phép cộng dồn phải chạy. Đây là ca biên nói thẳng ra chi phí của thuật toán này đến từ đâu.
- Mọi phần tử bằng nhau cho một mảng đếm có đúng một ô mang số 20 và 15 ô bằng 0, và chi phí không đổi một bước nào. Cả bốn kiểu dữ liệu trong sim đều cho 71 bước: sắp xếp đếm không nhìn thứ tự, nên nó không có ca tốt và cũng không có ca xấu.
- Dãy ngẫu nhiên sinh bằng bộ sinh giả ngẫu nhiên viết trong engine, không dùng đồng hồ và không dùng
Math.random. Cùng hạt giống thì cùng dãy, nên mọi con số trong bài bạn tái lập được từng chữ số.
Chặn dưới log₂(n!) chỉ áp cho thuật toán dựa trên so sánh, và sắp xếp đếm cùng sắp xếp theo cơ số không nằm trong lớp đó: chúng dùng giá trị làm địa chỉ và tiêu đúng 0 phép so sánh, trong khi ở n = 20 cái sàn kia là 62. Giá phải trả là mảng đếm dài bằng dải khai báo chứ không phải bằng dữ liệu: 20 phần tử trên dải 1 tới 1.000.000 cần 1.000.020 ô nhớ và 2.000.039 bước, chậm hơn thước so sánh 22.989 lần. Mốc hoà vốn ở n = 20 là k = 25, và mốc đó bò lên theo n, từ 2,34 ô mỗi phần tử ở n = 100 lên 5,64 ô ở n = 10.000. Sắp xếp theo cơ số cứu đúng ca dải rộng bằng cách đổi k thành ⌈log_b(k)⌉ lượt: cùng dữ liệu đó, cơ số 10 tốn 394 bước với 10 ô đếm. Và nó đứng trên tính ổn định: rải xuôi thay vì rải ngược làm dãy 21 12 11 22 ra 12 11 22 21, tức sai hẳn, từ lượt thứ hai trở đi.
- 1Sắp xếp đếm sắp xong 20 phần tử với 0 phép so sánh, trong khi bài trước chứng minh mọi thuật toán sắp xếp cần ít nhất 62 phép so sánh ở n = 20. Chỗ nào sai?
- 2Bạn có 20 số nguyên, mỗi số nằm đâu đó trong 1 tới 1.000.000. Vì sắp xếp đếm là O(n + k) nên bạn định dùng nó. Chuyện gì xảy ra?
- 3Bạn cài sắp xếp theo cơ số và viết vòng lặp rải chạy xuôi từ đầu mảng thay vì ngược từ cuối. Chạy thử trên 21 12 11 22, cơ số 10. Kết quả?