Bài 24. Hai cách sắp xếp khác: chọn dần và chèn dần
Ngoài cách đổi chỗ hai phần tử liền kề mà em đã học, còn hai lối sắp xếp rất tự nhiên khác: mỗi lượt chọn ra phần tử nhỏ nhất, hoặc lần lượt chèn từng phần tử vào đúng chỗ. Bài này mô phỏng, cài đặt và so sánh cả hai, rồi giới thiệu hai công cụ sắp xếp có sẵn của Python là sort() và sorted().
- Cánh DiềuTin học 11 (Khoa học máy tính) - Chủ đề F(CS) · Bài 9. Lập trình thuật toán sắp xếp nhanhtr. 127
- Kết nối tri thứcTin học 11 (Khoa học máy tính) - Bài 22. Thực hành bài toán sắp xếptr. 104–105
Bắt đầu bằng một hình dung
Chiều thứ Sáu, Minh và Lan được cô thủ thư nhờ dọn lại chồng phiếu mượn sách của cả tuần. Mỗi phiếu có một con số in ở góc, và chồng phiếu thì lộn xộn hoàn toàn vì bạn nào mượn xong cũng chỉ thả đại lên bàn. Cô dặn: xếp lại cho số nhỏ nằm trên cùng, số lớn nằm dưới cùng, để tuần sau còn tra cho nhanh.
Minh làm theo kiểu của cậu ấy. Cậu lướt mắt qua toàn bộ chồng phiếu, tìm ra tờ có số bé nhất, rút nó ra và đặt riêng sang một bên. Rồi cậu lại lướt qua chỗ phiếu còn lại, tìm tờ bé nhất trong đó, rút ra đặt tiếp xuống dưới tờ vừa rồi. Cứ thế, chồng bên trái ngày một dày lên và luôn luôn ngay ngắn, chồng bên phải thì vơi dần. Mỗi lần Minh chỉ nhấc tay đúng một lần, nhưng bù lại mắt cậu phải quét hết chỗ phiếu còn lại.
Lan thì làm khác hẳn. Cô ấy cầm chồng phiếu trên tay như cầm một cỗ bài, rút từng tờ một theo đúng thứ tự đang có, rồi luồn tờ vừa rút vào đúng khe của nó trong xấp phiếu đã ngay ngắn cầm ở tay trái - muốn luồn được thì phải đẩy mấy tờ có số lớn hơn nhích sang một chút. Tay cô ấy động đậy liên tục, nhưng mỗi tờ chỉ cần so với vài tờ gần đó là biết chỗ.
Cuối buổi, hai chồng phiếu đều thẳng thớm như nhau, và cô thủ thư chẳng phân biệt nổi cái nào do ai xếp. Nhưng hai bạn vừa vô tình diễn lại đúng hai thuật toán kinh điển của môn Tin học - và điểm khác nhau giữa hai cách làm ấy chính là nội dung bài học hôm nay.
Nội dung bài học
- 1) Sắp xếp chọn: mỗi lượt chọn ra phần tử nhỏ nhất
- 2) Sắp xếp chèn: xếp như người ta xếp bài trên tay
- 3) Ba thuật toán sắp xếp đơn giản khác nhau ở chỗ nào?
- 4) Trong thực tế: Python đã có sẵn sort() và sorted()
Tóm tắt lý thuyết cần nhớ
- Sắp xếp chọn mỗi lượt quét đoạn chưa sắp xếp để tìm phần tử nhỏ nhất rồi đổi chỗ nó về đầu đoạn; sau lượt thứ k, k phần tử đầu đã đúng vị trí vĩnh viễn.
- Khi cài đặt sắp xếp chọn, vòng trong chỉ ghi nhớ vị trí phần tử nhỏ nhất vào một biến, đến cuối lượt mới thực hiện một phép đổi chỗ duy nhất.
- Sắp xếp chèn lấy lần lượt từng phần tử của đoạn chưa sắp xếp, dịch các phần tử lớn hơn sang phải rồi luồn nó vào đúng khe - giống cách xếp bài trên tay.
- Cả ba thuật toán sắp xếp đơn giản đều là O(n²), nhưng sắp xếp chọn ít đổi chỗ nhất còn sắp xếp chèn rất nhanh khi dãy gần sắp sẵn; thực tế nên dùng
a.sort()(tại chỗ) hoặcsorted(a)(tạo danh sách mới), kèmreverse=Trueđể giảm dần.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| sort | xọt | sắp xếp Xếp các phần tử theo thứ tự tăng hoặc giảm - như xếp các bạn trong lớp theo chiều cao từ thấp đến cao. |
| list | lít | danh sách Một dãy nhiều giá trị xếp hàng, giống hộp bút có nhiều ô. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 24 câu, chấm điểm tự động và giải thích từng câu sai.
- So sánh và đổi chỗ hai phần tử đứng liền kề nhau mỗi khi chúng sai thứ tự.
- Chia dãy thành hai nửa, sắp xếp riêng từng nửa rồi trộn hai nửa lại với nhau.
- Lấy phần tử đầu tiên làm mốc rồi tách dãy thành nhóm nhỏ hơn mốc và nhóm lớn hơn mốc.
- Tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp rồi đổi chỗ nó về đầu đoạn chưa sắp xếp.
a = [5, 2, 8]. Sau khi thực hiện lệnh b = sorted(a), giá trị của a và b lần lượt là gì?- a = [5, 2, 8] và b = [2, 5, 8]
- a = [2, 5, 8] và b = [2, 5, 8]
- a = [2, 5, 8] và b = None
- a = [5, 2, 8] và b = None
sorted(a) không đụng đến danh sách gốc mà tạo ra và trả về một danh sách MỚI đã sắp xếp, nên a vẫn là [5, 2, 8] còn b là [2, 5, 8]. Phương án thứ hai sai vì nhầm sorted() với a.sort() - chỉ a.sort() mới sửa trực tiếp danh sách gốc. Hai phương án còn lại sai vì cho rằng sorted() trả về None; thực ra None là giá trị trả về của a.sort(), chứ không phải của sorted(a).- 4, 9, 7, 2, 6
- 2, 4, 7, 9, 6
- 2, 9, 4, 7, 6
- 2, 4, 6, 7, 9
- a)Trong sắp xếp chọn, sau khi kết thúc lượt thứ k thì k phần tử đầu dãy đã nằm đúng vị trí cuối cùng của chúng và không cần xét lại nữa.Đúng
- b)Sắp xếp chèn có độ phức tạp O(n log n) nên nhanh hơn hẳn sắp xếp chọn và sắp xếp nổi bọt trong mọi trường hợp.Sai
- c)Lệnh
a.sort()sắp xếp ngay trên danh sáchavà trả về giá trịNone, vì vậy viếta = a.sort()sẽ làm mất dữ liệu củaa.Đúng - d)Muốn sắp xếp một danh sách theo thứ tự giảm dần trong Python, bắt buộc phải tự viết lại thuật toán vì
sort()chỉ sắp được tăng dần.Sai
- (a) Đúng - đây chính là đặc điểm cốt lõi của sắp xếp chọn: mỗi lượt đưa được đúng một phần tử về vị trí vĩnh viễn, nên đoạn cần xét ở lượt sau ngắn hơn lượt trước một phần tử.
- (b) Sai - sắp xếp chèn vẫn là thuật toán O(n²) như hai thuật toán đơn giản kia; nó chỉ nhanh vượt trội trong trường hợp riêng là dãy đã gần được sắp sẵn, chứ không phải trong mọi trường hợp.
- (c) Đúng -
sort()là phương thức sắp xếp tại chỗ và trả vềNone, nên phép gána = a.sort()sẽ ghi đèNonelên danh sách vừa sắp xếp; muốn giữ dãy gốc phải dùngb = sorted(a). - (d) Sai - chỉ cần thêm tham số
reverse=True, chẳng hạna.sort(reverse=True)hoặcsorted(a, reverse=True), là có ngay thứ tự giảm dần mà không phải viết thêm dòng thuật toán nào.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 24 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.