Giáo án Bài 21 · KHMT. Các thuật toán sắp xếp đơn giản

Học sinh nhận ra nhu cầu sắp xếp một dãy số và huy động cách làm tự nhiên của mình, từ đó xác định nhiệm vụ của bài.

GV đưa dãy $[3,1,2]$ lên màn hình và hỏi: “Làm thế nào để đưa dãy này về thứ tự tăng dần bằng một quy trình rõ ràng, máy tính có thể làm theo được?”. HS suy nghĩ 1 phút, sau đó nêu cách làm của mình. Nhiệm vụ của cả lớp là so sánh các cách làm đó với ba thuật toán sẽ học trong bài.

Học sinh nêu được ít nhất một cách tự nhiên để sắp xếp dãy, ví dụ “tìm số nhỏ nhất rồi đặt lên đầu”, “lấy từng số đặt vào đúng chỗ”, “so sánh hai số kề nhau và đổi chỗ nếu sai”. Từ đó lớp thống nhất mục tiêu: hiểu cách hoạt động, vết các lượt và điều kiện áp dụng của ba thuật toán.

Học sinh nêu được ý tưởng của sắp xếp chọn và mô tả đúng kết quả từng lượt trên dãy $[3,1,2]$.

Học sinh làm việc theo cặp, theo dõi trên phiếu học tập số 1, phần A. Nhiệm vụ: với dãy $[3,1,2]$, ở mỗi lượt $i$ tìm phần tử nhỏ nhất trong đoạn chưa sắp từ vị trí $i$ đến hết, đổi chỗ với phần tử tại vị trí $i$, rồi ghi lại dãy sau mỗi lượt. Đặt câu hỏi: “Sau lượt đầu, đoạn nào được coi là đã sắp? Vì sao phần tử ở vị trí 0 không cần đổi nữa?”. GV nhắc HS giữ nguyên dãy gốc, làm việc trên bản sao.

Ý tưởng: ở mỗi lượt, đưa phần tử nhỏ nhất của đoạn chưa sắp về vị trí đầu đoạn đó. Vết: Ban đầu $[3,1,2]$. Lượt 1 ($i=0$): phần tử nhỏ nhất là $1$ ở vị trí 1, đổi với $3$, được $[1,3,2]$. Lượt 2 ($i=1$): trong đoạn $[3,2]$ phần tử nhỏ nhất là $2$, đổi với $3$, được $[1,2,3]$. Kết luận: sau mỗi lượt, đoạn đầu $0..i$ đã đúng thứ tự và không thay đổi nữa.

Học sinh nêu được ý tưởng của sắp xếp chèn, giải thích vai trò của việc lưu khoá trước khi dịch và mô tả đúng vết trên dãy $[3,1,2]$.

Học sinh làm việc theo cặp, ghi vết trên phiếu học tập số 1, phần B. Nhiệm vụ: bắt đầu từ $i=1$, lưu khoá $x=b[i]$; dịch sang phải các phần tử lớn hơn $x$ trong đoạn đầu đã sắp, rồi đặt $x$ vào chỗ trống. Làm với dãy $[3,1,2]$ và ghi dãy sau mỗi lần chèn. Đặt câu hỏi: “Vì sao phải lưu khoá trước khi dịch? Nếu không lưu thì điều gì xảy ra?”.

Ý tưởng: lấy phần tử mới ra làm khoá, dịch các phần tử lớn hơn khoá sang phải trong đoạn đầu đã sắp, rồi chèn khoá vào vị trí trống. Vết: Ban đầu $[3,1,2]$. Chèn lần 1 ($i=1$, khoá $1$): $3$ lớn hơn $1$ nên dịch sang phải, đặt $1$ vào đầu, được $[1,3,2]$. Chèn lần 2 ($i=2$, khoá $2$): $3$ lớn hơn $2$ nên dịch, $1$ nhỏ hơn $2$ nên dừng, đặt $2$ vào vị trí 1, được $[1,2,3]$. Nếu không lưu khoá, khi ghi đè $b[j+1]$ sẽ làm mất giá trị cần chèn.

Học sinh nêu được ý tưởng của nổi bọt theo quy ước quét trái sang phải, mô tả đúng vết một lượt và nêu được quy ước khi so sánh ba thuật toán.

Học sinh làm việc theo cặp, ghi vết trên phiếu học tập số 1, phần C và điền bảng so sánh ở phần D. Nhiệm vụ: với dãy $[3,1,2]$, quét từ trái sang phải một lượt, đổi hai phần tử kề nhau khi phần tử bên trái lớn hơn phần tử bên phải; ghi lại dãy sau mỗi lần đổi. Đặt câu hỏi: “Sau một lượt quét, phần tử nào chắc chắn nằm ở vị trí cuối?”. Nhắc HS: đây là một quy ước; nếu quét ngược chiều thì vết khác.

Ý tưởng: lặp lại việc đổi cặp kề sai thứ tự; sau mỗi lượt quét trái sang phải, phần tử lớn nhất của đoạn đang xét dồn về bên phải. Vết lượt đầu với $[3,1,2]$: so $3$ với $1$, sai nên đổi, được $[1,3,2]$; so $3$ với $2$, sai nên đổi, được $[1,2,3]$. Lượt đầu kết thúc với $[1,2,3]$. Lượt sau không còn cặp sai nên dừng.

Học sinh vận dụng được ba thuật toán để dự đoán và kiểm tra kết quả chương trình, nhận biết điều kiện bảo toàn số phần tử.

Học sinh làm việc theo cặp trên trang bài tập tương tác của NeoEdu hoặc làm trên phiếu học tập số 2. Nhiệm vụ: (1) Dự đoán rồi kiểm tra kết quả của các đoạn mã sắp xếp chọn trên $[3,1,2]$ (lấy phần tử thứ 1), $[4,4,1]$ (tính độ dài), $[-2,-5,0]$ (lấy phần tử đầu). (2) Chọn đáp án đúng về việc chọn làm gì mỗi lượt. (3) Xác định câu đúng/sai về việc bỏ giá trị trùng. (4) Sắp xếp các bước phương pháp giải. (5) Mô tả lượt đầu của ba thuật toán với $[3,1,2]$ và nêu sự khác nhau. GV đặt câu hỏi kiểm tra: “Chương trình in ra số nào? Vì sao?”.

Đáp án: (1) Dãy đã sắp $[1,2,3]$, phần tử thứ 1 là $2$. Dãy $[4,4,1]$ sau khi sắp có 3 phần tử, in $3$. Dãy $[-2,-5,0]$ sắp thành $[-5,-2,0]$, phần tử đầu là $-5$. (2) Đáp án A: chọn phần tử nhỏ nhất của phần chưa sắp và đưa về vị trí $i$. (3) Sai: sắp xếp phải bảo toàn số phần tử, không được bỏ giá trị trùng. (4) Thứ tự đúng: Sao chép dãy → Chọn nhỏ nhất phần còn lại → Đổi với đầu phần chưa sắp → Tiếp tục và kiểm tra bảo toàn. (5) Chọn lượt đầu: $[1,3,2]$; chèn lượt đầu: $[1,3,2]$; nổi bọt quét trái sang phải cả lượt: $[1,2,3]$. Sự khác nhau: chọn và chèn cùng cho $[1,3,2]$ nhưng theo cách khác; nổi bọt đổi nhiều cặp nên đến $[1,2,3]$; phải ghi quy ước lượt khi nêu kết quả.

Học sinh vận dụng sắp xếp chọn để sắp xếp danh sách điểm thi thực tế, kiểm tra kết quả và điều kiện áp dụng; có thể hoàn thành ở nhà.

Đề bài: Cho danh sách điểm kiểm tra của 6 bạn trong tổ, ví dụ $[7,5,8,5,9,6]$. Học sinh viết hàm sắp xếp chọn trên bản sao của danh sách, in ra danh sách đã sắp và điểm lớn nhất, nhỏ nhất. Kiểm tra: danh sách gốc có còn nguyên không; số lần xuất hiện của điểm $5$ có giữ nguyên không; nếu danh sách có chữ thay vì số thì thuật toán có áp dụng được không? Gợi ý: GV có thể yêu cầu HS tự tạo một danh sách điểm của mình và lưu kết quả vào vở.

Kết quả mẫu: danh sách sau khi sắp là $[5,5,6,7,8,9]$; điểm nhỏ nhất là $5$, điểm lớn nhất là $9$; hai số $5$ được giữ đủ. Điều kiện áp dụng: các phần tử phải so sánh được với nhau (cùng là số), danh sách gốc không bị đổi thứ tự, và số phần tử sau khi sắp phải bằng số phần tử ban đầu.