Ba thuật toán sắp xếp bậc hai
Ba thuật toán sắp xếp bậc hai, và vì sao chúng không giống nhau
Cả ba cùng O(n²). Đếm từng phép so sánh và từng phép dời chỗ thì hoá ra cái nhãn đó đang giấu một khoảng cách rất lớn.
Ở bài đếm phép tính bạn đã đếm số lần một dòng lệnh chạy, và ở bài bậc tăng bạn đã học cách bỏ hằng số để còn lại cái bậc. Ký hiệu O là một công cụ tốt, nhưng nó là một phép bỏ bớt thông tin có chủ ý, và bài này là chỗ dễ thấy nhất cái phần bị bỏ.
Ba thuật toán dưới đây, nổi bọt có cờ dừng sớm, chọn, và chèn, đều được xếp vào O(n²). Nghe như ba cái tương đương nhau, chỉ khác cách viết. Nhưng thử cho cả ba cùng chạy trên một mảng đã sắp sẵn 12 phần tử: sắp xếp chèn và nổi bọt tiêu đúng 11 phép so sánh rồi dừng, còn sắp xếp chọn vẫn cày hết 66 phép, tức gấp 6 lần, để rồi kết luận là không phải đổi chỗ gì cả. Cả ba vẫn là O(n²), và câu đó đúng, nhưng nó không hề mô tả cái vừa xảy ra.
Sim dưới đây chạy đủ ba thuật toán trên cùng một mảng và đếm chính xác hai thứ: số lần hai phần tử được đem ra so với nhau, và số lần một phần tử phải nằm sang ô khác. Mọi tham số đều sửa được, kể cả hạt giống của bộ sinh ngẫu nhiên, nên bạn có thể tự dựng lại mọi con số trong bài.
1 · Mảng vào ✎ sửa được
2 · Ba hoá đơn trên đúng mảng đó
| thuật toán | so sánh | dời chỗ | đổi chỗ | số lượt | dừng sớm |
|---|---|---|---|---|---|
| nổi bọt có cờ | 21 | 6 | 3 | 2 | ✓ có, cờ cắt còn 2 lượt |
| chọn | 66 | 6 | 3 | 11 | không có cờ, nên không có gì để cắt |
| chèn | 14 | 6 | 0, chèn chỉ dời | 11 | không có cờ, nên không có gì để cắt |
- So sánh: mỗi lần hai phần tử của mảng được đem ra so với nhau. So sánh chỉ số vòng lặp không tính, vì với bản ghi lớn thì phép so khoá mới là phép đắt.
- 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 lần dời. Một nhịp dời của sắp xếp chèn tính 1. Thả khoá vào chỗ trống tính thêm 1, nhưng chỉ khi nó thật sự sang ô khác, nên mảng đã sắp cho 0.
- Đổi chỗ là một phần của dời chỗ, đếm riêng vì sắp xếp chọn sống nhờ chính con số này. Sắp xếp chèn không bao giờ đổi chỗ.
3 · Công thức đoán trước, lần chạy xác nhận
| đại lượng | công thức, thay số của mảng này | công thức | chạy thật | khớp |
|---|---|---|---|---|
| chọn · so sánh | n(n−1)/2 = 12·11/2 | 66 | 66 | ✓ |
| chèn · so sánh | k + (n−1) − m = 3 + 11 − 0 | 14 | 14 | ✓ |
| chèn · nhịp dời | k = 3 | 3 | 3 | ✓ |
| nổi bọt · số lượt | min(n−1, D+1) = min(11, 2) | 2 | 2 | ✓ |
| nổi bọt · so sánh | tổng (n − p) với p chạy 1..2 | 21 | 21 | ✓ |
| nổi bọt · đổi chỗ | k = 3 | 3 | 3 | ✓ |
n là số phần tử, k là số cặp bị đảo, m là số vị trí nhỏ hơn hẳn mọi phần tử đứng trước nó (ở đó vòng quét của sắp xếp chèn chạy tuột khỏi mép trái nên bớt được một phép so sánh), D là quãng đường trái xa nhất một phần tử phải đi. Cả sáu dòng đều là số học phổ thông trên ba con số đọc thẳng từ dữ liệu, chưa cần chạy thuật toán lần nào.4 · Từng lượt một ✎ sửa được
| lượt | mảng sau lượt đó | so sánh | dời chỗ | chuyện gì xảy ra |
|---|---|---|---|---|
| 1 | 132456781191012 | 1 | 0 | lượt 1: ô 1 đã lớn hơn hàng xóm bên trái, đứng yên |
| 2 | 123456781191012 | 3 | 2 | lượt 2: dời 1 ô sang phải rồi thả ô 2 vào ô 1 |
| 3 | 123456781191012 | 4 | 2 | lượt 3: ô 3 đã lớn hơn hàng xóm bên trái, đứng yên |
| 4 | 123456781191012 | 5 | 2 | lượt 4: ô 4 đã lớn hơn hàng xóm bên trái, đứng yên |
| 5 | 123456781191012 | 6 | 2 | lượt 5: ô 5 đã lớn hơn hàng xóm bên trái, đứng yên |
| 6 | 123456781191012 | 7 | 2 | lượt 6: ô 6 đã lớn hơn hàng xóm bên trái, đứng yên |
| 7 | 123456781191012 | 8 | 2 | lượt 7: ô 7 đã lớn hơn hàng xóm bên trái, đứng yên |
| 8 | 123456781191012 | 9 | 2 | lượt 8: ô 8 đã lớn hơn hàng xóm bên trái, đứng yên |
| 9 | 123456789111012 | 11 | 4 | lượt 9: dời 1 ô sang phải rồi thả ô 9 vào ô 8 |
| 10 | 123456789101112 | 13 | 6 | lượt 10: dời 1 ô sang phải rồi thả ô 10 vào ô 9 |
| 11 | 123456789101112 | 14 | 6 | lượt 11: ô 11 đã lớn hơn hàng xóm bên trái, đứng yên |
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 | 3A1B3C2D1E | chưa sắp gì cả |
| nổi bọt có cờ | 1B1E2D3A3C | ✓ có, thứ tự cũ còn nguyên |
| chọn | 1B1E2D3C3A | ✗ không: cùng khoá 3, A vào trước C mà lại ra sau |
| chèn | 1B1E2D3A3C | ✓ có, thứ tự cũ còn nguyên |
- Nó đếm phép so sánh và phép dời chỗ. Nó không đo thời gian chạy. Thời gian thật còn phụ thuộc bộ nhớ đệm, kích thước bản ghi, và cách trình biên dịch xử lý vòng lặp, và ba thứ đó có thể đảo ngược thứ hạng ở đây.
- Cách quy giá một lần đổi chỗ thành 2 lần dời chỗ là một quy ước, không phải chân lý. Nếu bạn cài đổi chỗ bằng ba phép gán qua biến tạm thì con số là 3. Quy ước được ghi ra để bạn đọc bảng cho đúng, và nếu đổi quy ước thì mọi con số cột đó đổi theo cùng một hệ số.
- Ba thuật toán này không dùng cho dữ liệu lớn. Chúng ở đây vì chúng phơi ra rõ nhất chỗ ký hiệu
Olàm mất thông tin. Thư viện thật dùng thuật toán lai. - 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 ở kiểu gần như đã sắp: 12 phần tử, đúng 3 cặp bị đảo, hạt giống 2026, ra mảng 1 3 2 4 5 6 7 8 11 9 10 12. Ba hoá đơn như sau.
- Sắp xếp chèn: 14 phép so sánh. Nó đi từ trái sang, mỗi bước nhấc phần tử hiện tại lên rồi lùi dần về trái chừng nào còn gặp phần tử lớn hơn. Mảng gần đúng thứ tự thì nó lùi rất ít.
- Sắp xếp nổi bọt: 21 phép so sánh, 2 lượt. Lượt đầu quét 11 cặp kề nhau và đổi chỗ 3 lần. Lượt hai quét 10 cặp, không đổi chỗ lần nào, cờ báo dừng, và nó dừng thật.
- Sắp xếp chọn: 66 phép so sánh, 11 lượt. Nó không nhìn dữ liệu, nó chỉ chạy hai vòng lặp lồng nhau cho tới hết.
Chênh lệch giữa 14 và 66 là 52 phép so sánh, tức sắp xếp chọn tốn khoảng 4,71 lần sắp xếp chèn trên đúng mảng này. Cả ba đều O(n²).
Cột dời chỗ thì ngược lại: cả ba cùng ra 6. Nổi bọt và chọn mỗi cái đổi chỗ 3 lần, mỗi lần đổi chỗ làm hai phần tử sang ô khác nên tính 6. Sắp xếp chèn dời 3 nhịp rồi thả khoá xuống 3 lần, cũng ra 6. Nghĩa là ở trạng thái mở bài, toàn bộ khác biệt nằm ở cột so sánh, còn cột dời chỗ không tách được ba cái ra. Đây là lý do phải đếm hai thứ chứ không phải một.
Ba con số dự đoán được trước khi chạy
Mục 3 của sim không phải trang trí. Nó cho thấy ba hoá đơn kia không phải thứ bí ẩn phải chạy mới biết, mà tính thẳng ra được từ ba thống kê đọc ngay trên dữ liệu.
Sắp xếp chọn: đúng n(n-1)/2, bất kể dữ liệu. Hai vòng lặp của nó không hề có lệnh thoát sớm nào: vòng ngoài chạy từ 0 tới n-2, vòng trong quét hết phần đuôi. Cộng lại là (n-1) + (n-2) + ... + 1. Với n = 12 thì bằng 66, và bạn đổi kiểu dữ liệu kiểu gì đi nữa, con số đó vẫn 66. Nó là thuật toán duy nhất trong ba cái không đọc dữ liệu để quyết định làm gì tiếp.
Sắp xếp chèn: k + (n-1) - m. Ở đây k là số cặp bị đảo, tức số cặp vị trí i < j mà a[i] > a[j], và m là số vị trí, tính từ vị trí thứ hai trở đi, có giá trị nhỏ hơn hẳn mọi giá trị đứng trước nó. Lý do: mỗi lần vòng quét bước qua một phần tử lớn hơn, nó vừa tốn một phép so sánh vừa xoá đúng một cặp bị đảo, nên phần đó cộng lại thành k; ngoài ra mỗi phần tử còn tốn thêm một phép so sánh cuối cùng để biết là dừng, trừ những chỗ vòng quét chạy tuột khỏi mép trái mảng và không còn gì để so. Ở mảng mở bài: 3 + 11 - 0 = 14.
Nổi bọt: số lượt bằng min(n-1, D+1). D là quãng đường sang trái xa nhất mà một phần tử phải đi. Mỗi lượt kéo mọi phần tử cần đi sang trái đúng một bước, nên sau D lượt là mảng xong, và lượt thứ D+1 chạy để phát hiện ra không còn gì phải đổi. Mảng mở bài có D = 1 nên 2 lượt, và số phép so sánh là 11 + 10 = 21. Vòng lặp ngoài chỉ có n-1 lượt để tiêu, nên khi D lớn thì con số bị kẹp ở đó.
Cả ba công thức được cổng kiểm số đối chiếu với một lần chạy thật trên 783 cấu hình, và không có cấu hình nào lệch.
Khác biệt thứ nhất: mảng đã sắp sẵn
Bấm sang kiểu đã sắp, giữ 12 phần tử. Sắp xếp chèn 11, nổi bọt 11, chọn 66. Cả ba cùng 0 phép dời chỗ, vì không có gì sai chỗ.
Chuyện gì đã xảy ra: sắp xếp chèn và nổi bọt đều đọc dữ liệu để biết mình có việc hay không. Sắp xếp chèn so mỗi phần tử với hàng xóm bên trái, thấy lớn hơn là đứng yên, hết n-1 lần so là xong. Nổi bọt quét một lượt đầy đủ n-1 cặp, không đổi chỗ lần nào, cờ bật lên và nó thoát. Sắp xếp chọn không có cửa nào để nhận ra chuyện đó: nó phải quét cả phần đuôi mới dám nói phần tử nào nhỏ nhất.
Chú ý một chỗ dễ nói quá lời: n-1 và n(n-1)/2 bằng nhau khi n = 2, cả hai đều là 1. Nên câu "sắp xếp chọn luôn tốn nhiều hơn" là sai ở n = 2. Khoảng cách chỉ mở ra từ n = 3 trở đi, ở đó là 2 với 2 với 3. Cổng kiểm số khoá đúng chỗ đó, ở n = 1, n = 2 và n = 3, vì mốc biên là chỗ những câu khẳng định hay chết nhất.
Khác biệt thứ hai: khi phép dời chỗ mới là phép đắt
Cho tới giờ sắp xếp chọn nhìn như kẻ thua cuộc. Bấm sang kiểu đảo ngược, 12 phần tử, rồi nhìn cột dời chỗ.
Cả ba cùng 66 phép so sánh, cột đó không tách được ai với ai. Nhưng cột dời chỗ ra ba con số rất khác nhau: nổi bọt 132, chèn 77, chọn 12. Nổi bọt dời gấp 11 lần sắp xếp chọn.
Lý do nằm ngay trong tên của nó. Sắp xếp chọn quét cả phần đuôi để tìm phần tử nhỏ nhất, rồi đổi chỗ đúng một lần cho mỗi vị trí, và bỏ luôn lần đổi chỗ đó nếu phần tử nhỏ nhất đã nằm sẵn ở chỗ cần. Nên nó không bao giờ vượt quá n-1 lần đổi chỗ, dù dữ liệu tệ tới đâu. Trên mảng đảo ngược 12 phần tử nó chỉ cần 6 lần, vì mỗi lần đổi chỗ nó ghép luôn một cặp đầu đuôi.
Con số này quan trọng thật khi mỗi phần tử là một bản ghi lớn, ví dụ một struct vài trăm byte, hoặc một hàng dữ liệu phải ghi xuống đĩa. Lúc đó phép so sánh chỉ chạm vào khoá còn phép dời chỗ phải chép cả bản ghi, và 12 với 132 là hai thế giới khác nhau. Đó là ưu thế thật của sắp xếp chọn, và nó chỉ hiện ra khi bạn chịu đếm hai loại phép chứ không gộp tất cả vào một chữ O.
Nói cho sòng phẳng: cách quy một lần đổi chỗ thành 2 lần dời chỗ là một quy ước, không phải chân lý. Nếu bạn cài đổi chỗ bằng ba phép gán qua biến tạm thì mỗi lần đổi chỗ là 3. Đổi quy ước thì mọi con số cột đó nhân lên cùng một hệ số, còn thứ hạng giữa ba thuật toán thì không đổi.
Khác biệt thứ ba: mảng gần như đã sắp
Đây là ca hay gặp nhất trong thực tế: một danh sách đã sắp rồi, có thêm vài phần tử mới, hoặc vài phần tử bị sửa. Bấm sang kiểu gần như đã sắp rồi kéo núm số cặp bị đảo.
Núm đó không phải ước lượng. Mảng được dựng qua mã nghịch thế, tức chọn trước xem mỗi vị trí có bao nhiêu phần tử nhỏ hơn nằm sau nó, nên số cặp bị đảo ra đúng bằng con số bạn đặt. Cổng kiểm số đếm lại bằng hai thuật toán khác nhau, một vòng lặp đôi và một bộ đếm kiểu trộn, trên 1050 lần yêu cầu, không lần nào lệch.
Với 12 phần tử và hạt giống 2026, kéo núm từ 0 lên hết cỡ:
| cặp bị đảo | chèn | nổi bọt | chọn |
|---|---|---|---|
| 0 | 11 | 11 | 66 |
| 3 | 14 | 21 | 66 |
| 10 | 21 | 38 | 66 |
| 30 | 39 | 51 | 66 |
| 66 | 66 | 66 | 66 |
Cột chọn là một đường thẳng nằm ngang. Cột chèn bò lên gần như tuyến tính theo k. Trên 3188 bước kéo núm đã đo, không bước nào làm con số của sắp xếp chèn tụt xuống.
Một chỗ rất dễ viết sai, và chỉ đo lại mới lòi ra: sắp xếp chèn không phải đợi tới lúc mảng đảo ngược hoàn toàn mới chạm 66. Với hạt giống 2026 nó đã chạm 66 ngay từ k = 62, còn với hạt giống 1 thì từ k = 59. Nhìn công thức k + (n-1) - m là hiểu: khi mảng đã rất lộn xộn thì m cũng phình lên, nên hai vế đuổi kịp nhau sớm hơn. Cột chèn ở bảng trên là số của một hạt giống cụ thể, không phải hàm của riêng k.
Điều này có tên gọi riêng: sắp xếp chèn là thích ứng, chi phí của nó tỉ lệ với mức độ lộn xộn thật sự của dữ liệu chứ không tỉ lệ với kích thước mảng. Nổi bọt có cờ cũng thích ứng nhưng theo một thước đo khác hẳn: nó đếm lượt bằng D, tức quãng đường xa nhất, chứ không bằng tổng số cặp sai.
Khác biệt đó lớn tới đâu thì lấy một mảng dựng riêng ra tính bằng tay là thấy: 2 3 4 5 6 7 8 9 10 11 12 1, tức một dãy đã sắp mà phần tử nhỏ nhất bị đẩy xuống cuối. Mảng đó chỉ có 11 cặp bị đảo, ít thôi, nên sắp xếp chèn tiêu 11 + 11 - 1 = 21 phép so sánh. Nhưng D bằng 11, nghĩa là số 1 phải bò qua trọn 11 vị trí và mỗi lượt nổi bọt chỉ kéo nó được một bước, nên nổi bọt phải chạy đủ 11 lượt và tiêu trọn 66 phép so sánh, đúng bằng sắp xếp chọn. Một phần tử duy nhất nằm sai chỗ đủ xa là đủ xoá sạch lợi thế của cái cờ dừng sớm.
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 phần tử có khoá bằng nhau vẫn giữ nguyên thứ tự cũ sau khi sắp. Nghe trừu tượng, nên mục 5 của sim dựng ví dụ cụ thể: mỗi bản ghi là một cặp điểm số cộng một chữ cái ghi thứ tự lúc nộp.
Danh sách đầu là 3A 1B 3C 2D 1E. Cả ba thuật toán đều trả về đúng thứ tự điểm, nhưng:
- sắp xếp chèn và nổi bọt ra
1B 1E 2D 3A 3C, tức A vẫn đứng trước C như lúc vào; - sắp xếp chọn ra
1B 1E 2D 3C 3A, A và C đã đổi chỗ cho nhau.
Vì sao. Sắp xếp chèn và nổi bọt chỉ đổi chỗ hai ô kề nhau, và chỉ khi chúng thật sự sai thứ tự. Hai phần tử bằng nhau thì không sai thứ tự, nên chúng không bao giờ bị hoán vị. Sắp xếp chọn thì quăng phần tử nhỏ nhất từ xa về đầu đoạn, và cú quăng đó có thể nhảy qua đầu một phần tử bằng khoá. Ở danh sách trên, lượt lấy 1E về vị trí 1 đã hất 3A ra tận cuối, còn 3C ở lại phía trước.
Danh sách thứ hai là phản ví dụ ngắn nhất: 5A 5B 2C. Sắp xếp chọn thấy 2C nhỏ nhất, đổi chỗ nó với ô 0, và 5A bị ném ra sau 5B. Đúng một lần đổi chỗ là đủ phá.
Danh sách thứ ba tồn tại để bạn đừng nhớ sai chiều. 2A 1B 2C: sắp xếp chọn cũng đổi chỗ đúng một lần, nhưng lần đổi chỗ đó không chạm vào cặp trùng khoá, nên kết quả ra 1B 2A 2C, ổn định. Không ổn định nghĩa là không có bảo đảm, chứ không phải luôn luôn đảo. Nếu bạn cần bảo đảm thì phải chọn thuật toán ổn định, hoặc thêm chỉ số thứ tự vào làm khoá phụ.
Chuyện này không phải chi tiết học thuật. Sắp xếp bảng theo cột "ngày" rồi sắp lại theo cột "tên": nếu bước hai ổn định thì các dòng cùng tên vẫn nằm theo ngày. Không ổn định thì thứ tự đó biến mất.
Vậy dùng cái nào
Không cái nào, nếu dữ liệu lớn.
Ba thuật toán này có mặt trong bài vì chúng là chỗ rõ ràng nhất để thấy ký hiệu O làm mất thông tin gì, và vì bạn phải đọc trôi được một vòng lặp lồng nhau trước khi đọc được thứ phức tạp hơn. Trên vài chục phần tử thì chúng chạy nhanh và mã nguồn ngắn, sắp xếp chèn còn thường thắng cả những thuật toán "tốt hơn" ở kích thước nhỏ vì nó không tốn chi phí thiết lập. Nhưng cho vài chục nghìn phần tử thì n² là một bản án.
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ộng thêm vài cơ chế phòng ca xấu. Bài sau sẽ mổ đúng chỗ đó, và lúc ấy con số bạn vừa đo được ở đây sẽ là cái để so.
Vài điểm nhỏ nhưng hay bị bỏ qua:
- Sim đếm phép tính, không đo thời gian. Thời gian chạy thật còn phụ thuộc bộ nhớ đệm, kích thước bản ghi và cách trình biên dịch xử lý vòng lặp, và ba thứ đó có thể đảo ngược thứ hạng ở đây. Muốn nói về tốc độ thì phải bấm giờ, không phải đếm.
- Mảng rỗng và mảng một phần tử cho 0 phép so sánh ở cả ba thuật toán, và không lỗi. Kéo núm số phần tử về 0 để tự kiểm. Nhiều bản cài đặt hỏng đúng ở hai ca đó vì chỉ số vòng lặp chạy quá biên.
- 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ố. - Hạt giống đổi mảng nhưng không phải lúc nào cũng đổi hoá đơn. Ở trạng thái mở bài, cả 5 hạt giống được kiểm đều cho mảng khác nhau mà chỉ 1 trong 5 làm con số 14 nhúc nhích. Với 3 cặp bị đảo thì chi phí do số lượng cặp quyết định, chỗ chúng nằm hầu như không ảnh hưởng. Trên toàn dải đã quét thì hạt giống đổi hoá đơn ở 24 trên 28 cấu hình.
Cả ba thuật toán đều O(n²), và câu đó đúng nhưng che mất gần hết chuyện đáng biết. Trên mảng đã sắp 12 phần tử, sắp xếp chèn và nổi bọt có cờ tốn 11 phép so sánh, sắp xếp chọn tốn 66: cùng một bậc, gấp 6 lần. Sắp xếp chọn tốn đúng n(n-1)/2 phép so sánh bất kể dữ liệu, nhưng đổi lại nó không bao giờ quá n-1 lần đổi chỗ, nên trên mảng đảo ngược nó chỉ dời 12 lần trong khi nổi bọt dời 132, và đó là ưu thế thật khi bản ghi lớn. Sắp xếp chèn tốn khoảng k phép so sánh với k là số cặp bị đảo, nên nó thích ứng với dữ liệu gần đúng thứ tự. Chèn và nổi bọt ổn định vì chỉ đổi chỗ hai ô kề nhau khi chúng thật sự sai thứ tự; chọn thì không bảo đảm, và có phản ví dụ ba phần tử để chứng minh. Muốn so hai thuật toán cùng bậc thì phải đếm, và phải nói rõ đếm cái gì trên dữ liệu nào.
- 1Một mảng 8 phần tử đã sắp sẵn đúng thứ tự. Sắp xếp chọn tốn bao nhiêu phép so sánh?
- 2Mỗi phần tử là một bản ghi vài trăm byte, nên chép một bản ghi đắt hơn hẳn so hai khoá. Mảng 12 phần tử đang đảo ngược hoàn toàn. Chọn thuật toán nào và vì sao?
- 3Ba bản ghi vào theo thứ tự 5A, 5B, 2C, sắp theo điểm. Sau khi chạy sắp xếp chọn, hai bản ghi 5 điểm nằm thế nào?