Giáo án Bài 16. Thuật toán sắp xếp

Gợi nhớ khái niệm sắp xếp tăng dần và nhận ra có nhiều cách để đưa một dãy về đúng thứ tự, từ đó xác định nhiệm vụ học tập của bài.

GV mời 4 HS lên bảng, mỗi HS cầm một thẻ số theo thứ tự 5, 2, 4, 1. Cả lớp quan sát và trả lời câu hỏi: “Làm thế nào để xếp bốn thẻ này theo thứ tự tăng dần, và có bao nhiêu cách làm?” Sau đó HS thử đưa ra ít nhất hai cách làm khác nhau trên bảng.

• Dãy tăng dần đúng là 1, 2, 4, 5 (bốn số giữ nguyên, không bỏ số nào).
• HS nêu được ít nhất hai cách: (1) tìm số nhỏ nhất rồi đổi với vị trí đầu; (2) đổi chỗ các cặp sai thứ tự cho đến khi dãy tăng.
• Nhiệm vụ học tập: hiểu hai thuật toán sắp xếp chọn và nổi bọt, thực hiện từng lượt và kiểm tra kết quả.

Giải thích được thuật toán sắp xếp chọn và thực hiện đúng các lượt sắp xếp tăng dần của dãy 5, 2, 4, 1 theo cách đổi ngay khi gặp phần tử nhỏ hơn.

Nhóm 4 HS làm Phiếu học tập số 1 (sắp xếp chọn). Nhiệm vụ: xét vị trí $i$, lần lượt so sánh giá trị đang ở vị trí $i$ với từng phần tử phía sau; gặp phần tử nhỏ hơn thì đổi ngay. Ghi trạng thái dãy sau từng lần đổi cho $i = 1$, $i = 2$ và $i = 3$. Sau đó nhóm trả lời: “Vì sao sau lượt $i = 1$ số 1 đã đúng vị trí đầu?” và “Lượt $i = 3$ còn cần làm gì?”. Nhóm có thể mở trang NeoEdu, phần ví dụ sắp xếp chọn, để đối chiếu.

• Lượt $i = 1$: 5, 2, 4, 1 → 2, 5, 4, 1 (so 5 với 2, đổi) → giữ khi so 2 với 4 → 1, 5, 4, 2 (so 2 với 1, đổi). Trạng thái cuối lượt: 1, 5, 4, 2.
• Lượt $i = 2$: 1, 5, 4, 2 → 1, 4, 5, 2 (so 5 với 4, đổi) → 1, 2, 5, 4 (so 4 với 2, đổi). Trạng thái cuối lượt: 1, 2, 5, 4.
• Lượt $i = 3$: 1, 2, 5, 4 → 1, 2, 4, 5 (so 5 với 4, đổi). Trạng thái cuối: 1, 2, 4, 5.
• Sau lượt $i = 1$, số 1 là nhỏ nhất của cả dãy nên đứng đúng vị trí đầu và không cần đổi nữa.
• Kiến thức rút ra: sắp xếp chọn xử lí từng vị trí theo thứ tự; mỗi lượt đưa đúng một phần tử vào vị trí cố định.

Mô tả được thuật toán sắp xếp nổi bọt, chỉ đổi chỗ các phần tử kề nhau và thực hiện đúng ba lượt cho dãy 5, 2, 4, 1.

Nhóm 4 HS làm Phiếu học tập số 2 (sắp xếp nổi bọt). Nhiệm vụ: ở mỗi lượt, duyệt các cặp kề nhau từ cuối phần chưa sắp về đầu; nếu phần tử sau nhỏ hơn phần tử trước thì đổi chỗ. Ghi trạng thái sau từng lượt. Nhóm trả lời câu hỏi: “Vì sao sau lượt đầu số 1 đã đứng đầu dãy? Vì sao không được đổi hai phần tử không kề nhau?”

• Lượt 1 (từ phải sang trái): 5, 2, 4, 1 → 5, 2, 1, 4 (đổi 4 với 1) → 5, 1, 2, 4 (đổi 2 với 1) → 1, 5, 2, 4 (đổi 5 với 1). Trạng thái cuối lượt 1: 1, 5, 2, 4.
• Lượt 2 trên phần chưa sắp 5, 2, 4: cặp 2 và 4 giữ nguyên; cặp 5 và 2 đổi → 1, 2, 5, 4. Trạng thái cuối lượt 2: 1, 2, 5, 4.
• Lượt 3: cặp 5 và 4 đổi → 1, 2, 4, 5.
• Giải thích: sau lượt 1, số 1 nhỏ nhất đã nổi lên đầu nên không cần xét lại; sau lượt 2, hai vị trí đầu đã đúng.
• Đổi chỗ hai phần tử không kề nhau không phải là một bước nổi bọt.

Giải thích được điểm khác nhau giữa hai thuật toán, chia bài toán thành bài toán nhỏ và giải thích vì sao phải di chuyển cả bản ghi khi sắp xếp.

GV tổ chức trao đổi theo cặp đôi với ba câu hỏi: (1) Hai thuật toán khác nhau ở cách xét phần tử nào? (2) Vì sao sau khi vị trí đầu đã chứa phần tử nhỏ nhất, ta có thể xử lí đoạn còn lại bằng cùng nguyên tắc? (3) Danh sách gồm tên và điểm: vì sao không được sắp riêng cột điểm?

• Chọn trực tiếp: xét từng vị trí cố định và so với các phần tử phía sau. Nổi bọt: xét các cặp kề nhau và đưa phần tử nhỏ nhất lên đầu sau mỗi lượt.
• Sau khi vị trí đầu đã đúng, phần còn lại là một bài toán nhỏ hơn có cùng cách giải; kết quả từng đoạn ghép lại thành dãy tăng.
• Với bản ghi, phải di chuyển cả bản ghi (tên cùng điểm) để không gán điểm cho sai người. Sắp riêng cột điểm có thể làm điểm bị gán sai người.

Củng cố khái niệm sắp xếp tăng, giảm, đổi chỗ, bảo toàn phần tử và điều kiện sắp xếp bản ghi qua các câu hỏi nhanh.

HS làm nhanh các câu hỏi sau theo nhóm 2, dùng bảng con hoặc giơ thẻ đáp án.
Câu 1: Mục tiêu tăng dần là gì? A. Phần tử sau không nhỏ hơn phần tử trước; B. Xóa số lớn; C. Chỉ giữ số đầu; D. Đổi mọi số thành 0.
Câu 2: Sau chọn nhỏ nhất lượt đầu của 5, 2, 4, 1 là dãy nào? A. 2, 5, 4, 1; B. 1, 2, 4, 5; C. 1, 5, 2, 4; D. 5, 4, 2, 1.
Câu 3: Sắp xếp được phép tự xóa giá trị lặp (Đúng/Sai).
Câu 4: Bảng có tên và điểm phải sắp cả hàng để giữ đúng người–điểm (Đúng/Sai).
Câu 5: Ghép khái niệm với tác dụng: Tăng dần, Giảm dần, Đổi chỗ.
Câu 6: Sắp xếp tăng dãy 5, 2, 4, 1 bằng cách chọn nhỏ nhất của phần chưa sắp: sắp xếp các bước theo thứ tự trước–sau.
Câu 7: Trong sắp xếp chọn đổi ngay, dãy 5, 2, 4, 1 sau lượt đầu là dãy nào? A. 1, 2, 4, 5; B. 1, 5, 4, 2; C. 1, 5, 2, 4; D. 2, 5, 4, 1.

• Câu 1: A (tăng không nghiêm cho phép giá trị bằng nhau).
• Câu 2: B (đổi 1 với 5, các phần tử giữa giữ nguyên).
• Câu 3: Sai (phải bảo toàn dữ liệu; hai số bằng nhau vẫn là hai phần tử).
• Câu 4: Đúng (sắp riêng cột điểm có thể gán điểm sai người).
• Câu 5: Tăng dần – sau không nhỏ hơn trước; Giảm dần – sau không lớn hơn trước; Đổi chỗ – hoán vị hai phần tử.
• Câu 6: Tìm nhỏ nhất toàn dãy là 1 rồi đổi với 5 → trong đoạn 2, 4, 5 chọn 2 giữ vị trí thứ 2 → trong đoạn 4, 5 chọn 4 giữ vị trí thứ 3 → xác nhận dãy tăng và giữ đủ bốn phần tử. Sau lượt 1: 1, 2, 4, 5; lượt 2 và 3 không đổi.
• Câu 7: B (5 gặp 2 thì đổi thành 2, 5, 4, 1; 2 gặp 4 không đổi; 2 gặp 1 đổi thành 1, 5, 4, 2).

Vận dụng được hai thuật toán để sắp xếp các dãy số, giải thích kết quả và kiểm tra điều kiện bảo toàn số lặp.

Nhóm 4 HS làm ba bài sau, mỗi bài ghi đủ trạng thái và kết quả. Bài 1: sắp tăng dãy 5, 2, 4, 1 bằng cách chọn nhỏ nhất của phần chưa sắp rồi đổi với vị trí đầu phần đó; ghi đủ thao tác và kết quả. Bài 2: sắp tăng dãy 3, 1, 3, 2 và giải thích số 3 có còn hai lần không. Bài 3: sắp tăng 5, 2, 4, 1 bằng nổi bọt; viết đủ ba trạng thái sau từng lượt và giải thích phần đã cố định.

• Bài 1: lượt 1: đổi 1 với 5 được 1, 2, 4, 5; các lượt sau không đổi. Dãy đúng và đủ: 1, 2, 4, 5. Thang điểm gợi ý: lượt 1 (0,4); lượt tiếp theo (0,2); dãy đúng và đủ (0,2); mô tả thuật toán (0,2).
• Bài 2: dãy 1, 2, 3, 3. Hai số 3 vẫn còn vì sắp xếp chỉ đổi vị trí, không lọc trùng. Thang điểm gợi ý: dãy đúng (0,5); bảo toàn số lặp và giải thích (0,5).
• Bài 3: lượt 1: 5, 2, 1, 4 → 5, 1, 2, 4 → 1, 5, 2, 4 (số 1 đã ở đầu). Lượt 2: từ 1, 5, 2, 4, giữ cặp 2 và 4, đổi 5 với 2 → 1, 2, 5, 4. Lượt 3: đổi 5 với 4 → 1, 2, 4, 5. Hai vị trí đầu đã đúng sau lượt 2. Thang điểm: lượt 1 (0,3); lượt 2 (0,3); lượt 3 (0,2); giải thích phần đầu đã cố định (0,2).

Vận dụng được thuật toán sắp xếp để sắp xếp một danh sách bản ghi thực tế, giữ đúng cặp tên–điểm và tự kiểm tra kết quả.

Tổ trưởng ghi bảng điểm kiểm tra gần đây của 5 bạn trong tổ (chỉ dùng dữ liệu giả định hoặc đã được cho phép), mỗi bản ghi một dòng gồm tên và điểm. Nhiệm vụ: sắp xếp danh sách theo điểm giảm dần bằng một trong hai thuật toán đã học, ghi rõ thuật toán đã chọn, mỗi bản ghi di chuyển cùng tên. Sau khi sắp, nhóm kiểm tra: danh sách có đủ 5 bạn, mỗi bạn vẫn đúng điểm, và điểm từ trên xuống không tăng. Bài này có thể giao về nhà cho các tổ khác hoặc làm bằng bảng tính đơn giản nếu lớp có máy tính.

• Sản phẩm: danh sách 5 bản ghi (tên, điểm) được sắp theo điểm giảm dần, ghi rõ thuật toán đã dùng và các lượt đổi chỗ.
• Kiểm tra: đủ 5 bạn; mỗi tên vẫn đi cùng điểm của mình; điểm từ trên xuống không tăng.
• Kiến thức vận dụng: sắp xếp bản ghi phải di chuyển cả bản ghi; sắp xếp giảm dần thì phần tử sau không lớn hơn phần tử trước.