Thuật toán sắp xếp
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | sắp xếp nổi bọt |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | sắp xếp chèn |
| in place/ɪn pleɪs/ | ngay tại chỗ |
| stable/ˈsteɪbl/ | ổn định |
Sắp xếp chậm một cách cố ý
- Mọi thư viện nghiêm túc đều sử dụng thuật toán sắp xếp mà đề thi không yêu cầu bạn viết. Sắp xếp nổi và sắp xếp chèn đều là $O(n^2)$, và cả hai đều kém hơn bất kỳ thuật toán sắp xếp tốt nào trên danh sách lớn.
- Chúng vẫn nằm trong chương trình học vì một lý do tốt: chúng ngắn đủ để theo dõi bằng tay, và việc theo dõi một thuật toán là cách bạn học thuật toán sắp xếp thực sự làm gì với mảng.
- Cũng có một trường hợp thực tế cho sắp xếp chèn. Trên danh sách nhỏ hoặc gần như đã sắp xếp, nó thực sự là thứ nhanh nhất, và các thư viện thực tế chuyển sang dùng nó đúng cho những trường hợp đó.
- Bài học này là sắp xếp nổi và sắp xếp chèn: các thuật toán, hành vi của chúng, và nơi mỗi thuật toán chiến thắng.
Sắp xếp nổi bọt
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- Mỗi lượt so sánh cặp phần tử kề nhau và hoán đổi bất kỳ cặp nào không đúng thứ tự, nên giá trị lớn còn lại "nổi" lên cuối cùng.
- Sau lượt $k$, $k$ phần tử cuối cùng đã cố định, đó là lý do vòng lặp bên trong dừng ở $n - \text{pass}$.
- Cờ
swappedcho phép nó dừng sớm: nếu một lượt hoàn toàn không có hoán đổi, danh sách đã được sắp xếp.
Sắp xếp chèn
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- Nó xây dựng một phần đã sắp xếp ở phía trước, mở rộng thêm một phần tử mỗi lần. Mỗi phần tử mới được giữ tạm thời là
key, các phần tử lớn hơn được dịch sang phải để mở khoảng trống, và khóa được đặt vào. - Đây là cách hầu hết mọi người sắp xếp một bộ bài, đó là ví dụ tương đương mà đề thi mong đợi.
Phía trái đã sắp xếp, phía phải chưa thay đổi, và ranh giới di chuyển sang phải
Thuật toán sắp xếp
so sánh các phần tử kề nhau, hoán vị nếu cần
Trải qua một lần sắp xếp nổi bọt: mỗi lượt di chuyển giá trị lớn nhất lên cuối cùng.
Sắp xếp nổi bọt hoạt động bằng cách:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi lượt hoán vị các cặp phần tử kề nhau, "nổi" phần tử lớn nhất lên cuối cùng.
Độ phức tạp thời gian trung bình/xấu nhất của sắp xếp nổi bọt là:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Hai vòng lặp lồng nhau trên n phần tử cho O(n²); trường hợp tốt nhất (đã sắp xếp) là O(n) với việc thoát sớm.
Ví dụ minh họa: theo dõi một lượt
- Theo dõi lượt đầu tiên của sắp xếp nổi trên 5, 3, 8, 1.
- So sánh 5 và 3: sai thứ tự, hoán đổi, cho 3, 5, 8, 1. So sánh 5 và 8: đúng thứ tự, không hoán đổi. So sánh 8 và 1: hoán đổi, cho 3, 5, 1, 8.
- Sau một lượt, giá trị lớn nhất, 8, đã ở vị trí cuối cùng, và từ giờ trở đi có thể bỏ qua một phép so sánh mỗi lượt.
- Bây giờ theo dõi bước thứ ba của sắp xếp chèn trên 3, 5, 8, 1. Khóa là 1. Dịch 8, 5 và 3 mỗi cái một vị trí sang phải, sau đó đặt 1 ở đầu: 1, 3, 5, 8. Hiển thị mảng sau mỗi bước; đó là nơi điểm số nằm.
Sắp xếp chèn xây dựng kết quả đã sắp xếp bằng cách:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Nó mở rộng một tiền tố đã sắp xếp ở bên trái, dịch các phần tử lớn hơn sang phải để đặt mỗi khóa vào đúng vị trí.
Sắp xếp chèn đặt mỗi phần tử mới như thế nào?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Giữ khóa ra ngoài và dịch chuyển là điểm phân biệt với việc hoán vị liên tục các phần tử kề nhau của sắp xếp nổi bọt.
Hiệu suất
| Nổi | Chèn | |
|---|---|---|
| Trường hợp tốt nhất | $O(n)$, một lượt không có hoán đổi | $O(n)$, đã sắp xếp sẵn, không cần dịch |
| Trung bình và xấu nhất | $O(n^2)$ | $O(n^2)$ |
| Bộ nhớ bổ sung | $O(1)$, ngay tại chỗ | $O(1)$, ngay tại chỗ |
| Ổn định | Có | Có, ổn định |
- Ngay tại chỗ có nghĩa là nó chỉ cần một lượng bộ nhớ phụ không đổi, sắp xếp ngay trong bản thân mảng. Ổn định có nghĩa là hai giá trị bằng nhau giữ nguyên thứ tự tương đối ban đầu, điều này quan trọng khi danh sách đã được sắp xếp theo một trường khác.
- Cả hai đều đạt $O(n)$ trên dữ liệu đã sắp xếp, nhưng chỉ nếu sắp xếp nổi có cờ
swapped. Không có nó, nó luôn thực hiện đầy đủ tất cả các lượt.
Sau lượt đầu tiên của sắp xếp nổi bọt trên 5, 3, 8, 1, mảng sẽ là gì? Viết bốn số cách nhau bởi dấu phẩy.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
5 và 3 hoán vị, 5 và 8 không hoán vị, 8 và 1 hoán vị. Giá trị lớn nhất đã đến cuối, nên lượt tiếp theo có thể ngắn đi một phép so sánh.
Ví dụ minh họa: thuật toán sắp xếp nào, và tại sao
- Một danh sách 200,000 bản ghi phải được sắp xếp lại từ đầu. Không cái nào cả: cả hai đều là $O(n^2)$, nên cần sắp xếp gộp hoặc sắp xếp nhanh ở mức độ $O(n \log n)$. Hãy nói rõ thay vì chọn phương án ít tệ nhất.
- Một danh sách đã sắp xếp 10,000 nhận thêm 5 bản ghi mới ở cuối và phải sắp xếp lại. Sắp xếp chèn: dữ liệu gần như đã được sắp xếp, nên mỗi khóa mới chỉ dịch chuyển một đoạn ngắn và thời gian tiến gần đến $O(n)$.
- Một ví dụ giảng dạy phải được theo dõi bằng tay trên giấy. Sắp xếp nổi: nó dễ theo dõi nhất, đó là công dụng thực tế còn sót lại của nó.
- Justify từ trạng thái của dữ liệu và kích thước, không phải từ sở thích chung chung.
Gắn mỗi khái niệm sắp xếp với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Sắp xếp nổi bọt hoán vị hàng xóm, sắp xếp chèn mở rộng tiền tố đã sắp xếp; cả hai đều là O(n²) trường hợp xấu nhất; tính ổn định liên quan đến thứ tự của các khóa bằng nhau.
Sắp xếp chèn chạy gần O(n) trên mảng nhỏ hoặc gần như đã sắp xếp, vì ít phần tử cần được dịch chuyển.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Trên dữ liệu gần như đã sắp xếp, mỗi phần tử mới gần như đã ở đúng chỗ — đó là lý do sắp xếp chèn vượt trội hơn các thuật toán phức tạp hơn trên đầu vào nhỏ.
Điều nào đúng cho cả sắp xếp nổi bọt và sắp xếp chèn? Chọn tất cả các đáp án đúng.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Trên danh sách lớn không sắp xếp, thuật toán sắp xếp O(n log n) chiến thắng rõ rệt. Khẳng định điều đó là câu trả lời đúng, chứ không phải chọn cái kém tồi tệ nhất trong hai cái.
Tại sao một lượt không phải là toàn bộ câu chuyện
- Cả hai thuật toán sắp xếp đều thực hiện nhiều lượt lặp, và đề thi phân biệt chúng dựa vào việc một lượt đạt được gì và khi nào chúng dừng lại.
- Một lượt sắp xếp nổi so sánh các cặp phần tử kề nhau và hoán đổi chúng, nên một lượt mang phần tử lớn còn lại đến vị trí cuối cùng. Toàn bộ quá trình sắp xếp bao gồm $n - 1$ lượt.
- Một lượt sắp xếp chèn lấy phần tử tiếp theo và đưa nó trở về phần đã sắp xếp, nên sau $k$ lượt, $k$ phần tử đầu tiên đã được sắp xếp trong nội bộ nhưng chưa ở vị trí cuối cùng.
- Sắp xếp nổi có thể được cải thiện bằng cờ: nếu một lượt không có hoán đổi, danh sách đã được sắp xếp và thuật toán dừng lại. Trên dữ liệu gần như đã sắp xếp, điều biến nó thành chỉ một lượt.
- Không có cờ, cả hai đều là $n^2$ trong trường hợp xấu nhất, đó là lý do cả hai đều là lựa chọn kém cho tập tin lớn và vì sao đề thi hỏi về các tập nhỏ.
Một danh sách đã sắp xếp gồm 10,000 bản ghi nhận thêm 5 bản ghi mới ở cuối. Loại sắp xếp nào phù hợp để sắp xếp lại?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Dữ liệu gần như đã sắp xếp chính là trường hợp tốt nhất của thuật toán chèn, tiến tới O(n). Các thư viện thực tế chuyển sang sử dụng nó vì lý do này.
Khớp mỗi thuật toán sắp xếp với những gì một lượt chạy đạt được.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Sự khác biệt đó chính là điều mà câu hỏi theo dõi (trace) thực sự kiểm tra. Cờ trong bubble-sort cũng cho phép nó dừng sớm trên dữ liệu gần như đã sắp xếp, điều mà insertion sort vốn xử lý rất tốt.
Điểm số dễ mất
- Sắp xếp nổi so sánh các cặp phần tử kề nhau. Một câu trả lời so sánh một phần tử với tất cả các phần tử khác đang mô tả một thuật toán khác.
- Vòng lặp bên trong rút ngắn mỗi lần chạy, vì phần cuối của mảng đã được sắp xếp. Hãy giải thích tại sao.
- Sắp xếp chèn dịch chuyển các phần tử sang phải để tạo khoảng trống; nó không hoán vị liên tục. Sự khác biệt này chính là điểm mấu chốt của thuật toán.
- Cả hai đều có độ phức tạp $O(n^2)$ trung bình và trường hợp xấu nhất, và $O(n)$ ở trường hợp tốt nhất. Hãy nêu ví dụ minh họa cho từng trường hợp đó.
Bạn đã nắm vững
- Sắp xếp bong bóng: thực hiện nhiều lượt so sánh các cặp kề nhau và hoán vị, phần tử lớn nhất nổi lên cuối mảng, vòng lặp bên trong rút ngắn mỗi lượt, với một cờ
swappedđể thoát sớm. - Sắp xếp chèn: mở rộng phần đã sắp xếp ở đầu mảng, giữ tạm mỗi khóa (key), dịch chuyển các phần tử lớn hơn sang phải rồi thả khóa vào khoảng trống.
- Cả hai đều có độ phức tạp $O(n^2)$ trung bình và xấu nhất, $O(n)$ tốt nhất, nguyên tại chỗ và bền vững.
- Sắp xếp chèn thực sự vượt trội trên danh sách nhỏ hoặc gần như đã sắp xếp; còn đối với danh sách lớn chưa sắp xếp thì cả hai đều không phải lựa chọn tối ưu.