Sắp xếp nhanh, và vì sao nó có thể chậm
Sắp xếp nhanh, và vì sao nó có thể chậm
Tên nó là nhanh. Nhưng chỉ cần chọn chốt sai một lần là nó tiêu đúng bằng sắp xếp chọn, và đào một ngăn xếp sâu bằng cả mảng.
Ở bài ba thuật toán sắp xếp bậc hai bạn đã đếm từng phép so sánh của nổi bọt, chọn và chèn, và thấy nhãn O(n²) giấu đi bao nhiêu thứ. Ở bài sắp xếp trộn bạn đã gặp ý tưởng chia để trị: cắt đôi, giải hai nửa, rồi ghép lại. Bài này là người anh em của nó, đi theo chiều ngược lại, và bài này có một chỗ mà sắp xếp trộn không có: nó có thể hỏng.
Sắp xếp nhanh làm đúng ba việc. Chọn một phần tử làm chốt. Phân hoạch mảng sao cho mọi thứ nhỏ hơn hoặc bằng chốt nằm bên trái nó, mọi thứ lớn hơn nằm bên phải. Rồi gọi lại chính nó trên hai bên. Sau bước phân hoạch, chốt đã ở đúng chỗ của nó trong kết quả cuối và không bao giờ phải dịch nữa. Đó là toàn bộ tiến bộ mà một lần phân hoạch tạo ra: đúng một phần tử được chốt cứng.
Câu hỏi duy nhất còn lại là hai bên được chia thế nào. Chia đôi đều thì cây đệ quy cao khoảng log₂n và tổng chi phí khoảng n log n. Chia lệch hẳn, tức một bên rỗng, thì cây đệ quy cao đúng n và tổng chi phí đúng n(n−1)/2. Cùng một dòng mã, khác nhau ở chỗ chốt rơi vào đâu. Sim dưới đây cho bạn bấm đúng cái đó.
1 · Mảng vào ✎ sửa được
2 · Bốn cách chọn chốt trên đúng mảng đó
| chốt là | so sánh | dời chỗ | đổi chỗ | phân hoạch | độ sâu | chạm trần bậc hai |
|---|---|---|---|---|---|---|
| phần tử đầu | 38 | 28 | 14 | 7 | 7 | ✓ không, còn cách trần 28 phép |
| phần tử cuối | 44 | 20 | 10 | 9 | 8 | ✓ không, còn cách trần 22 phép |
| phần tử giữa | 27 | 32 | 16 | 8 | 5 | ✓ không, còn cách trần 39 phép |
| trung vị của ba | 45 | 28 | 14 | 6 | 6 | ✓ không, còn cách trần 33 phép · trong đó 12 phép chỉ để chọn chốt |
- So sánh: mỗi lần hai phần tử của mảng được đem ra so với nhau, đúng quy ước của bài ba thuật toán bậc hai. So sánh chỉ số vòng lặp không tính. Phép so sánh mà trung vị của ba tiêu để chọn chốt có tính, vì nó cũng là so sánh dữ liệu thật, và đó là lý do cách chọn đó không miễn phí.
- Dời chỗ: mỗi lần một phần tử nằm sang ô khác. Một lần đổi chỗ làm hai phần tử đổi ô nên tính 2. Đổi chỗ một ô với chính nó không dời gì cả nên không tính, giống hệt cách sắp xếp chọn bỏ qua cú đổi chỗ vô nghĩa của nó.
- Phân hoạch ở đây là kiểu Lomuto: đưa chốt về cuối đoạn, quét từ trái sang giữ một ranh giới sao cho mọi thứ bên trái ranh giới đều
≤chốt, rồi đặt chốt ngay sau ranh giới. Nó tiêu đúng(độ dài đoạn − 1)phép so sánh, bất kể dữ liệu. Chính vì con số đó cố định mà mọi công thức trong bài này là số chính xác chứ không phải xấp xỉ. - Phần tử bằng chốt đi về bên trái. Đó là một quy ước, và nó là nguyên nhân trực tiếp của cả hai điều tệ nhất trong bài: mảng toàn phần tử bằng nhau tụt xuống bậc hai, và thứ tự cũ của các khoá bằng nhau bị phá.
3 · Từng lần phân hoạch, với chốt là phần tử đầu ✎ sửa được
| lần | độ sâu | mảng sau lần đó | so sánh | dời chỗ | chuyện gì xảy ra |
|---|---|---|---|---|---|
| 1 | 1 | 123108749611125 | 11 | 4 | độ sâu 1, đoạn [0..11] dài 12: chốt 2 về ô 1, chia thành 1 và 10 |
| 2 | 2 | 123108749611125 | 20 | 8 | độ sâu 2, đoạn [2..11] dài 10: chốt 3 về ô 2, cắt lệch hẳn thành 0 và 9 |
| 3 | 3 | 123587496101211 | 28 | 12 | độ sâu 3, đoạn [3..11] dài 9: chốt 10 về ô 9, chia thành 6 và 2 |
| 4 | 4 | 123457698101211 | 33 | 18 | độ sâu 4, đoạn [3..8] dài 6: chốt 5 về ô 4, chia thành 1 và 4 |
| 5 | 5 | 123456798101211 | 36 | 24 | độ sâu 5, đoạn [5..8] dài 4: chốt 7 về ô 6, chia thành 1 và 2 |
| 6 | 6 | 123456789101211 | 37 | 26 | độ sâu 6, đoạn [7..8] dài 2: chốt 9 về ô 8, cắt lệch hẳn thành 1 và 0 |
| 7 | 4 | 123456789101112 | 38 | 28 | độ sâu 4, đoạn [10..11] dài 2: chốt 12 về ô 11, cắt lệch hẳn thành 1 và 0 |
4 · Ngăn xếp đệ quy và bộ nhớ phụ ✎ sửa được
n, nên mảng đầu tiên làm tràn có 10.001 phần tử. Nếu mọi lần cắt đều chia đôi thì độ sâu là ⌊log₂n⌋ + 1, và mảng đầu tiên làm tràn phải có tới 3.011 chữ số phần tử, tức không tồn tại. Cùng một thuật toán, cùng một ngăn xếp, và khoảng cách giữa hai con số đó là toàn bộ giá trị của việc chọn chốt cho tử tế.n, tức 12 khung, và một khung hàm còn to hơn một ô mảng. Câu đúng là: sắp xếp nhanh tốn O(độ sâu), và độ sâu là thứ bạn phải tự bảo đảm, không phải thứ được cho không.5 · Hai bản ghi bằng điểm nhau thì ai đứng trước ✎ 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 | 3A3B1C | chưa sắp gì cả |
| chốt phần tử đầu | 1C3B3A | ✗ không: cùng khoá 3, A vào trước B mà lại ra sau |
| chốt phần tử cuối | 1C3B3A | ✗ không: cùng khoá 3, A vào trước B mà lại ra sau |
| chốt phần tử giữa | 1C3A3B | ✓ có, thứ tự cũ còn nguyên |
| chốt trung vị của ba | 1C3B3A | ✗ không: cùng khoá 3, A vào trước B mà lại ra sau |
- Nó đếm phép so sánh và phép dời chỗ. Nó không đo thời gian chạy. Sắp xếp nhanh nổi tiếng nhanh phần lớn là nhờ nó chạy tại chỗ và đi tuần tự qua bộ nhớ, tức nhờ bộ nhớ đệm, và ở đây không có gì đo được chuyện đó.
- Số khung ngăn xếp là một núm, không phải hằng số. Ngân sách thật phụ thuộc kích thước ngăn xếp của luồng và độ lớn mỗi khung. Đo thử trên Node.js v24.14.0 ngày 29/07/2026 bằng cách gọi đệ quy một hàm có đúng hình dạng lời gọi của sắp xếp nhanh lệch hẳn một bên, đếm số khung tới lúc bắt được RangeError, lặp 5 lần trong cùng một tiến trình: năm lần chạy cho 18.379, 20.867, 20.867, 20.867, 20.867. Ngay trong một tiến trình nó đã không ổn định, nên mọi con số ở mục 4 là số học trên giả định của bạn, không phải phép đo môi trường nào.
- Chỉ có một kiểu phân hoạch ở đây, kiểu Lomuto. Kiểu Hoare tiêu ít phép đổi chỗ hơn và xử lý mảng nhiều khoá trùng khá hơn hẳn, nhưng nó là một thuật toán khác và không được cài trong engine này, nên bài không nói gì về số của nó.
- Không có yếu tố ngẫu nhiên trong thuật toán. Bốn cách chọn chốt ở đây đều tất định, nên mọi ca xấu nhất trong bài đều tái lập được. Chốt ngẫu nhiên thật sẽ làm ca xấu nhất khó gặp đi, nhưng nó cần một nguồn ngẫu nhiên và engine này không có: dãy “ngẫu nhiên” ở mục 1 là dữ liệu sinh bằng bộ sinh giả ngẫu nhiên có hạt giống, không phải chốt ngẫu nhiên.
- Dãy dựng riêng để hạ chốt giữa được dựng nhắm vào đúng bản phân hoạch này. Đổi chi tiết cài đặt thì phải dựng lại dãy khác. Nó chứng minh chốt giữa có phản ví dụ, chứ không nói gì về phản ví dụ của các cách chọn khác.
Trạng thái mở bài đang nói gì
Sim khởi động ở kiểu ngẫu nhiên có hạt giống, 12 phần tử, hạt giống 2026, ra mảng 2 5 3 10 8 7 4 9 6 11 12 1. Đây đúng là mảng của bài trước, cùng bộ sinh và cùng hạt giống, nên bạn so được từng con số giữa hai bài. Cách chọn chốt đang là phần tử đầu.
Bốn hoá đơn trên đúng mảng đó:
| chốt là | so sánh | dời chỗ | phân hoạch | độ sâu |
|---|---|---|---|---|
| phần tử đầu | 38 | 28 | 7 | 7 |
| phần tử cuối | 44 | 20 | 9 | 8 |
| phần tử giữa | 27 | 32 | 8 | 5 |
| trung vị của ba | 45 | 28 | 6 | 6 |
Ba con số để đọc bảng này cho đúng. Trần bậc hai là 66, tức 12·11/2, là chi phí khi mọi lần cắt đều lệch hẳn. Chi phí lý tưởng là 25, tức chi phí nếu chốt rơi trúng trung vị mọi lần. Trần độ sâu là 12 còn độ sâu nếu chia đôi đều là 4, tức ⌊log₂12⌋ + 1.
Không cách chọn chốt nào ở đây chạm trần, và cả bốn đều trả về mảng đã sắp. Nhưng để ý một chỗ ngược đời: trung vị của ba đang là cách đắt nhất, 45 phép so sánh. Lý do nằm ngay trong bảng của sim: 12 trong 45 phép đó không phân hoạch gì cả, chúng chỉ để chọn chốt. Trên mảng 12 phần tử thì cái giá đó nuốt hết phần tiết kiệm được. Ghi lại con số 12 này, lát nữa nó quay lại.
Phân hoạch làm được đúng một việc
Bấm mở mục 3 của sim và đọc dòng đầu tiên. Đoạn [0..11], chốt lấy từ ô 0 nên giá trị chốt là 2, và sau khi phân hoạch xong chốt nằm ở ô 1. Bên trái nó có 1 phần tử, bên phải có 10. Lần phân hoạch đó tiêu 11 phép so sánh.
Con số 11 không phải ngẫu nhiên. Cách phân hoạch cài trong sim là kiểu Lomuto: đưa chốt về cuối đoạn, rồi quét một lượt từ trái sang, so từng phần tử với chốt đúng một lần. Đoạn dài m ô thì có m−1 ô phải so, nên mọi lần phân hoạch tiêu đúng m−1 phép so sánh, bất kể dữ liệu. Đây là lý do mọi công thức trong bài này ra số chính xác chứ không phải xấp xỉ, và nó cũng là lý do câu hỏi duy nhất đáng hỏi là "hai bên được chia thế nào".
Vì đúng một phần tử được chốt cứng mỗi lần, tổng chi phí là tổng của m−1 trên mọi đoạn từng xuất hiện. Nếu mỗi lần đoạn ngắn đi một, tức một bên luôn rỗng, thì tổng đó là (n−1) + (n−2) + ... + 1, đúng bằng n(n−1)/2. Nếu mỗi lần đoạn chia đôi thì tổng đó là con số 25 kia. Cả hai đều tính được trước khi chạy.
Chỗ nó sụp: mảng đã sắp cộng chốt đầu
Giữ nguyên chốt đầu, bấm kiểu dữ liệu sang đã sắp.
Số phép so sánh nhảy từ 38 lên 66. Độ sâu nhảy từ 7 lên 12.
66 chính là trần n(n−1)/2. Và 66 cũng chính là con số sắp xếp chọn tiêu ở bài trước trên đúng mảng 12 phần tử đã sắp đó. Không phải "cùng bậc", mà cùng con số, từng đơn vị. Cổng kiểm số của bài này biên dịch luôn engine của bài trước và đối chiếu trực tiếp, ở mọi n từ 0 tới 28, để câu trên không phải là thứ tôi nhớ mang máng.
Vì sao. Mảng đã sắp thì ô đầu đoạn luôn là phần tử nhỏ nhất của đoạn. Chốt nhỏ nhất nghĩa là không có gì nhỏ hơn nó, nên bên trái rỗng, còn bên phải nhận trọn phần còn lại. Đoạn ngắn đi đúng một ô mỗi lần, và ta rơi vào đúng cái tổng (n−1) + (n−2) + ... ở trên.
Một chỗ rất dễ nhớ sai, và chỉ đo lại mới lòi ra. Nghe tên "chốt đầu chết trên mảng đã sắp" thì phản xạ tự nhiên là "vậy chốt cuối chết trên mảng đảo ngược". Bấm thử cả bốn tổ hợp:
| chốt đầu | chốt cuối | |
|---|---|---|
| đã sắp | 66 | 66 |
| đảo ngược | 66 | 66 |
Cả bốn ô đều là 66. Chốt cuối không hề đối xứng theo cách đó: nó chết trên cả hai kiểu, y hệt chốt đầu. Lý do là phân hoạch không quan tâm chốt lớn hay nhỏ, nó chỉ quan tâm chốt có phải cực trị hay không. Chốt là lớn nhất thì bên phải rỗng, chốt là nhỏ nhất thì bên trái rỗng, và rỗng bên nào cũng lệch hẳn như nhau. Khác biệt duy nhất giữa hai ô nằm ở cột dời chỗ: trên mảng đã sắp, chốt cuối tiêu 0 phép dời chỗ còn chốt đầu tiêu 44, vì chốt cuối đã nằm sẵn ở chỗ mà phân hoạch cần đưa nó tới.
Trung vị của ba, và cái giá của nó
Vẫn giữ đã sắp, giờ bấm sang trung vị của ba. Con số tụt từ 66 xuống 37, độ sâu tụt từ 12 xuống 4.
Tách 37 ra thì thấy chuyện gì đã xảy ra: 25 phép cho phân hoạch cộng 12 phép để chọn chốt. Con số 25 đúng bằng chi phí lý tưởng của n = 12, tức chốt đã rơi trúng trung vị mọi lần, không lệch lần nào. Con số 4 đúng bằng ⌊log₂12⌋ + 1. Cách chọn chốt này lấy trung vị của ba ô đầu, giữa và cuối, và trên một mảng đã sắp thì ô giữa chính là trung vị thật, nên nó luôn chọn đúng.
Nhưng đừng dừng ở đó, vì cột bên cạnh đang nói một chuyện khó chịu. Trên đúng mảng ấy, chốt giữa tiêu 25, tức rẻ hơn trung vị của ba. Nó cũng đạt độ sâu 4. Nó chọn đúng cái ô mà trung vị của ba phải mua bằng 12 phép so sánh, và nó không trả đồng nào.
Điều đó không có nghĩa chốt giữa tốt hơn. Nó có nghĩa là thông tin không miễn phí, và trên dữ liệu này thông tin đó thừa. Trung vị của ba trả tiền cho một bảo hiểm mà mảng đã sắp không cần tới. Muốn biết cái bảo hiểm đó đáng giá bao nhiêu thì phải tìm chỗ mà chốt giữa đoán trượt, và chỗ đó có thật.
Chốt giữa không an toàn, chỉ là chưa gặp phản ví dụ
Bấm kiểu dữ liệu sang dãy dựng riêng để hạ chốt giữa. Ở 12 phần tử, mảng đó là 2 4 6 8 10 12 3 7 1 9 5 11.
Chốt giữa tiêu 66 phép so sánh và đào độ sâu 12, tức chạm cả hai cái trần. Trên đúng dãy đó, chốt đầu chỉ tiêu 31. Cái mà chốt giữa vừa gặp không phải xui: dãy này được dựng bằng cách chạy ngược chính phép phân hoạch trong sim, gán cho ô chính giữa của mỗi đoạn giá trị lớn nhất còn lại, nên chốt giữa luôn vớ phải phần tử lớn nhất của đoạn. Cổng kiểm số dựng lại dãy đó cho mọi n từ 2 tới 28 và xác nhận nó chạm trần đúng từng cỡ một.
Chuyện này tổng quát hơn một dãy. Cổng kiểm số quét cạn mọi hoán vị cỡ nhỏ, tức 120 hoán vị ở n = 5, 720 ở n = 6, 5.040 ở n = 7 và 40.320 ở n = 8, chạy cả bốn cách chọn chốt trên từng hoán vị, rồi hỏi cách nào chạm được trần bậc hai. Kết quả:
- chốt đầu, chốt cuối và chốt giữa đều chạm trần ở cả bốn cỡ. Không phải suy luận, mà là có dãy cụ thể in ra được: ở
n = 8, dãy hạ chốt giữa mà phép quét tìm thấy là1 4 6 8 2 5 3 7, và chạy lại đúng dãy đó cho ra đúng 28 phép so sánh và độ sâu 8. - trung vị của ba không chạm trần trên hoán vị nào tới
n = 8.
Nói cho sòng phẳng về ý thứ hai: đó là một khẳng định về n tới 8, không phải một chứng minh. Không tìm thấy phản ví dụ trong 40.320 dãy không có nghĩa là không tồn tại ở n lớn hơn. Người ta biết cách dựng dãy hạ trung vị của ba, chỉ là những dãy đó dài hơn cái mà một phép quét cạn với tay tới được. Bài này chỉ nói được đúng cái nó đo được.
Ca mà không cách chọn chốt nào cứu được
Bấm sang toàn phần tử bằng nhau.
| chốt là | so sánh | trong đó chọn chốt | độ sâu |
|---|---|---|---|
| phần tử đầu | 66 | 0 | 12 |
| phần tử cuối | 66 | 0 | 12 |
| phần tử giữa | 66 | 0 | 12 |
| trung vị của ba | 96 | 30 | 12 |
Cả bốn cùng chạm trần, cùng đào độ sâu bằng n. Và cái mẹo cứu được ba ca trước, trung vị của ba, ở đây là cách tệ nhất: 96 phép so sánh, tức vượt cả trần bậc hai, vì 30 phép chọn chốt của nó chồng lên một lần chạy vốn đã bậc hai rồi. Cổng kiểm số xác nhận cả bốn cùng tụt xuống bậc hai ở mọi n từ 2 tới 28, chứ không riêng ở 12. Riêng khoản vượt trần của trung vị của ba thì chỉ đúng từ n = 3 trở lên: ở n = 2 đoạn ngắn tới mức không có ba ứng viên để lấy trung vị, nên luật này lùi về ô giữa và không tiêu phép nào để chọn chốt, cả bốn cùng ra đúng 1 phép so sánh.
Nguyên nhân nằm ở một dòng quy ước trong phép phân hoạch: phần tử bằng chốt đi về bên trái. Khi cả mảng bằng nhau thì mọi phần tử đều bằng chốt, nên tất cả đổ về một bên, bên kia rỗng, và ta lại ở đúng ca xấu nhất. Không cách chọn chốt nào chữa được, vì mọi ô đều giống hệt nhau: chọn ô nào cũng là chọn cùng một giá trị.
Đây không phải ca hiếm gặp trong phòng thí nghiệm. Sắp một bảng theo cột trạng thái mà cả bảng cùng một trạng thái, sắp một danh sách theo cột năm mà tất cả cùng năm, sắp theo một cột cờ chỉ có hai giá trị: dữ liệu thật đầy khoá trùng. Cách chữa thật không nằm ở chốt mà nằm ở phân hoạch: chia làm ba phần, nhỏ hơn chốt, bằng chốt, lớn hơn chốt, rồi chỉ đệ quy vào hai phần ngoài. Sim này không cài cách đó, nên bài không nêu con số nào cho nó.
Độ sâu đệ quy, và lúc ngăn xếp vỡ
Cột độ sâu trong bảng không phải trang trí. Mỗi lời gọi đệ quy còn dang dở là một khung nằm trên ngăn xếp, giữ chỗ cho biến cục bộ và địa chỉ quay về, đúng như bài hàm đệ quy đã mô tả. Số phép so sánh nhiều thì chương trình chạy lâu; ngăn xếp sâu quá thì chương trình chết, và nó chết đột ngột chứ không chậm dần.
Mục 4 của sim biến cái đó thành số học. Đặt ngân sách ngăn xếp là 10.000 khung:
- ca xấu nhất cho độ sâu đúng bằng
n, nên mảng đầu tiên làm tràn chỉ cần 10.001 phần tử. Mười nghìn phần tử là một mảng bé tí, và nếu nó tình cờ đã sắp sẵn thì chốt đầu đủ để giết chương trình. - cắt cân bằng cho độ sâu
⌊log₂n⌋ + 1, nên mảng đầu tiên làm tràn phải có 3.011 chữ số phần tử. Con số đó không tồn tại và sẽ không bao giờ tồn tại.
Cùng một thuật toán, cùng một ngăn xếp, và khoảng cách giữa 10.001 với một số 3.011 chữ số là toàn bộ giá trị của việc chọn chốt cho tử tế. Kéo núm ngân sách để xem hai con số chạy theo.
Hai điều phải nói rõ về con số 10.000. Thứ nhất, nó là một núm chứ không phải hằng số: ngân sách thật phụ thuộc kích thước ngăn xếp của luồng và độ lớn mỗi khung, và không thứ gì trong bài này đo được hai cái đó. Thứ hai, tôi có thử đo một lần cho có cái neo. Trên Node.js v24.14.0, ngày 29/07/2026, gọi đệ quy một hàm có đúng hình dạng lời gọi của sắp xếp nhanh lệch hẳn một bên và đếm số khung tới lúc bắt được lỗi, năm lần chạy trong cùng một tiến trình cho ra 18.379 rồi 20.867 bốn lần liên tiếp. Ngay trong một tiến trình nó đã không ổn định. Đó là lý do bài để bạn tự đặt ngân sách chứ không ghim một con số và gọi nó là sự thật.
Còn cách chữa thì có thật, và nó rẻ. Cột độ sâu nếu đệ quy vào nửa nhỏ trong sim tính đúng cây đệ quy đó nhưng xếp khung theo kiểu khác: gọi đệ quy vào nửa ngắn hơn, rồi thay vì gọi tiếp vào nửa dài, thì lặp lại vòng ngoài với nửa dài đó, tái dùng luôn khung đang có. Trên ca xấu nhất mà độ sâu ngây thơ là 12, con số này là 1. Cổng kiểm số chứng minh nó không bao giờ vượt ⌊log₂n⌋ + 1 trên toàn bộ lưới đã quét, và đó chính là toàn bộ lý do mẹo này tồn tại. Nó cũng không phải phép màu: trên một cây cân bằng hoàn hảo, ví dụ 15 phần tử đã sắp với chốt giữa, hai con số bằng nhau, đều là 4.
Bộ nhớ phụ: so với sắp xếp trộn
Sắp xếp trộn cần một mảng phụ đầy đủ để ghép hai nửa vào, tức n ô nhớ, và con số đó cố định, không phụ thuộc dữ liệu. Ở 12 phần tử là 12 ô.
Sắp xếp nhanh không cần mảng phụ nào: nó đảo chỗ ngay trên mảng gốc. Chỗ tốn thêm duy nhất của nó là ngăn xếp đệ quy. Ở trạng thái mở bài, đó là 7 khung. Với mẹo nửa nhỏ, 2 khung.
Chỗ này rất dễ viết quá tay, nên phải nói cho chính xác. Câu sai là "sắp xếp nhanh luôn tốn ít bộ nhớ hơn sắp xếp trộn". Ở ca xấu nhất, độ sâu bằng n, tức 12 khung cho mảng 12 phần tử, và một khung hàm còn to hơn một ô mảng vì nó giữ nhiều biến cộng địa chỉ quay về. Ở đúng ca đó, sắp xếp nhanh tốn nhiều hơn sắp xếp trộn.
Câu đúng là: sắp xếp nhanh tốn O(độ sâu) bộ nhớ phụ, còn sắp xếp trộn tốn O(n). Sắp xếp nhanh thắng khi và chỉ khi độ sâu được giữ ở mức log n, và độ sâu là thứ bạn phải tự bảo đảm, bằng cách chọn chốt và bằng mẹo nửa nhỏ, chứ không phải thứ được cho không. Sắp xếp trộn thì tốn n ô trong mọi ca, kể cả ca xấu nhất, và cái mọi ca đó chính là thứ đáng giá của nó.
Tính ổn định, nhìn thấy chứ không nghe kể
Một thuật toán sắp xếp gọi là ổn định khi hai bản ghi có khoá bằng nhau vẫn giữ nguyên thứ tự cũ sau khi sắp. Ở bài trước, sắp xếp chèn và nổi bọt ổn định vì chúng chỉ đổi chỗ hai ô kề nhau khi hai ô đó thật sự sai thứ tự. Sắp xếp nhanh không ổn định, và mục 5 của sim dựng ví dụ để bạn nhìn thấy chứ không phải nghe kể.
Danh sách đầu tiên là phản ví dụ ngắn nhất: 3A 3B 1C. Khoá chính là điểm, chữ cái ghi thứ tự lúc nộp, nên A vào trước B.
- chốt đầu, chốt cuối và trung vị của ba đều ra
1C 3B 3A. B đã nhảy qua đầu A. - chốt giữa ra
1C 3A 3B, tức giữ nguyên.
Chuyện gì xảy ra với chốt đầu. Chốt là 3A. Phân hoạch đưa chốt về cuối đoạn, tức 3A bị ném xuống ô 2. Rồi 1C nhỏ hơn nên về đầu, và 3B ở lại giữa. Đúng một cú ném là đủ. Đây chính là chỗ sắp xếp nhanh khác hẳn sắp xếp chèn: nó ném phần tử đi rất xa, chứ không đổi chỗ hai ô kề nhau, nên hai phần tử bằng khoá hoàn toàn có thể nhảy qua đầu nhau.
Bấm sang danh sách thứ hai, 2A 3B 1C 3D 2E 1F, và đổi qua lại bốn cách chọn chốt. Mỗi cách phá một cặp khác nhau: chốt đầu phá cặp khoá 2, chốt cuối phá cặp khoá 3, chốt giữa phá cặp khoá 1, còn trung vị của ba không phá cặp nào.
Đọc kết quả đó cho đúng chiều là việc khó nhất ở đây, nên nói thẳng cả hai phía.
- Không có cách chọn chốt nào an toàn. Chốt đầu phá cả ba danh sách trong sim. Việc trung vị của ba giữ nguyên ở danh sách thứ hai là chuyện của đúng danh sách đó, không phải một tính chất.
- Nhưng "luôn luôn đảo" cũng sai. Danh sách nào trong sim cũng có ít nhất một cách chọn chốt không phá gì. Danh sách thứ ba,
1A 2B 2C, còn cho thấy cặp trùng nằm ở hai ô cuối vẫn bị đảo bởi ba trong bốn cách, và cách còn lại tránh được hoàn toàn do may.
Câu đúng là không bảo đảm. Cần bảo đảm thì phải thêm chỉ số thứ tự vào làm khoá phụ, hoặc dùng một thuật toán ổn định, và sắp xếp trộn là một thuật toán như vậy.
Vậy dùng cái nào
Sắp xếp nhanh vẫn là lựa chọn mặc định trong rất nhiều thư viện, và không phải vì số phép so sánh của nó nhỏ hơn. Ở bậc tăng thì nó và sắp xếp trộn cùng O(n log n). Nó thắng ở những thứ mà sim này không đo được: nó chạy tại chỗ nên không phải cấp phát mảng phụ, và nó quét bộ nhớ tuần tự nên bộ nhớ đệm rất ưa. Muốn nói về tốc độ thì phải bấm giờ, không phải đếm, và ở đây tôi chỉ đếm.
Cái sim này đo được là giá phải trả để có được điều đó:
- phải chọn chốt tử tế, vì ba cách chọn ngây thơ đều có dãy hạ chúng xuống bậc hai, và cổng kiểm số đã tìm ra dãy đó cho từng cách;
- phải chặn độ sâu, vì ngăn xếp không cảnh báo trước khi vỡ;
- phải xử lý khoá trùng, vì mảng toàn phần tử bằng nhau hạ cả bốn cách chọn chốt;
- và phải chấp nhận mất tính ổn định, hoặc tự mua lại bằng khoá phụ.
Bài trước có nói thư viện thật dùng thuật toán lai, chia để trị cho phần lớn rồi chuyển sang sắp xếp chèn khi đoạn còn lại đã đủ nhỏ. Câu đó vẫn đúng, và bốn gạch đầu dòng trên chính là danh sách những chỗ mà một thư viện thật phải vá. Ngưỡng chuyển cụ thể của một thư viện cụ thể thì tôi chưa kiểm được trong lúc viết bài này, nên bài không nêu con số nào cho nó. Con số duy nhất bạn nên mang đi là con số bạn tự bấm ra được ở trên.
Sắp xếp nhanh chỉ làm một việc mỗi lần phân hoạch: chốt một phần tử vào đúng chỗ, với giá đúng m−1 phép so sánh trên đoạn dài m. Toàn bộ số phận của nó nằm ở chỗ hai bên chia thế nào. Trên mảng 12 phần tử đã sắp, chốt đầu tiêu 66 phép so sánh, đúng bằng n(n−1)/2 và đúng bằng con số sắp xếp chọn của bài trước, với độ sâu đệ quy 12 tức bằng cả mảng. Đổi sang trung vị của ba thì còn 37, trong đó chỉ 25 là phân hoạch còn 12 là tiền mua thông tin, và độ sâu tụt về 4. Nhưng chốt giữa trên đúng mảng đó chỉ tốn 25, nên trung vị của ba không phải luôn thắng: nó mua bảo hiểm, và bảo hiểm có phí. Ba cách chọn chốt ngây thơ đều có dãy hạ chúng xuống trần, phép quét cạn 40.320 hoán vị đã tìm ra từng dãy một, và mảng toàn phần tử bằng nhau hạ cả bốn, với trung vị của ba tiêu 96 tức vượt cả trần. Về bộ nhớ, sắp xếp nhanh tốn O(độ sâu) chứ không phải O(1): với ngăn xếp 10.000 khung, một mảng 10.001 phần tử đã sắp là đủ làm tràn, trừ khi bạn đệ quy vào nửa nhỏ, và lúc đó độ sâu tụt từ 12 xuống 1. Cuối cùng nó không ổn định: 3A 3B 1C với chốt đầu ra 1C 3B 3A, đúng một cú ném là đủ phá.
- 1Một mảng 8 phần tử đã sắp sẵn đúng thứ tự, chạy sắp xếp nhanh với chốt là phần tử đầu đoạn. Số phép so sánh và độ sâu đệ quy là bao nhiêu?
- 2Bạn phải sắp một bảng 12 dòng theo một cột mà cả 12 dòng đều cùng một giá trị. Đổi cách chọn chốt sang trung vị của ba có cứu được không?
- 3Ba bản ghi vào theo thứ tự 3A, 3B, 1C, sắp theo điểm bằng sắp xếp nhanh với chốt là phần tử đầu. Hai bản ghi 3 điểm nằm thế nào, và vì sao?