Giáo án NLS Tin học 11 KHMT kết nối Bài 21: Các thuật toán sắp xếp đơn giản
Giáo án NLS Tin học 11 (Khoa học máy tính) kết nối tri thức Bài 21: Các thuật toán sắp xếp đơn giản. Với năng lực số được tích hợp, tiết học sẽ giúp học sinh làm quen và ứng dụng công nghệ, tin học. KHBD này là file word, tải về dễ dàng. Là mẫu giáo án mới nhất năm 2026 để giáo viên dạy tốt môn Tin học 11.
Xem: => Giáo án tích hợp NLS Tin học 11 Khoa học máy tính Kết nối tri thức
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
I. MỤC TIÊU:
1. Kiến thức:
Học xong bài này, HS đạt các yêu cầu sau:
- Biết và thực hiện được một số thuật toán sắp xếp đơn giản.
2. Năng lực
Năng lực chung:
- Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập trong lớp.
- Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của GV.
- Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.
Năng lực riêng:
- Biết và thực hiện được một số thuật toán sắp xếp đơn giản.
- Thực hiện được các thuật toán và chương sắp xếp đơn giản như sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.
Năng lực số:
- 6.2.NC1a: Sử dụng Chatbot AI để tạo bảng mô phỏng từng bước chạy (Trace Table) của thuật toán, giúp hình dung sự thay đổi vị trí của các phần tử trong mảng.
- 5.2.NC1a: Viết và tối ưu hóa mã nguồn Python cho các thuật toán sắp xếp, sử dụng các cấu trúc điều khiển (vòng lặp lồng nhau) chính xác.
- 1.2.NC1a: Phân tích dữ liệu đầu vào (mảng chưa sắp xếp) và kết quả đầu ra (mảng đã sắp xếp) để kiểm chứng tính đúng đắn của thuật toán.
- 2.4.NC1a: Sử dụng công cụ trực quan hóa (như Python Tutor hoặc tính năng Code Interpreter của AI) để quan sát luồng dữ liệu.
3. Phẩm chất
- Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
1. Đối với giáo viên
- SGK, tài liệu giảng dạy, giáo án PPT.
- Máy tính, máy chiếu.
- Video AI tạo bằng công cụ AI được dùng để khởi động bài học.
2. Đối với học sinh:
- SGK, SBT Tin học 11, vở ghi chép.
- Tài liệu, thiết bị có liên quan đến nội dung bài học.
- Thiết bị di động/máy tính có kết nối Internet (sử dụng theo nhóm).
III. TIẾN TRÌNH DẠY HỌC
A. HOẠT ĐỘNG KHỞI ĐỘNG
a) Mục tiêu: HS biết được về bài toán sắp xếp các phần tử của một danh sách theo thứ tự (tăng dần hoặc giảm dần) và ý nghĩa của việc sắp xếp trong bài toán tìm kiếm.
b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu, thông qua đó làm quen với các thuật toán sắp xếp đơn giản.
c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra.
d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ:
- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.
- GV dẫn dắt, đặt vấn đề cho HS: Bài học trước cho em thấy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn so với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. Bài toán sắp xếp cơ bản có dạng như sau:
Cho dãy A gồm n phần tử:
A[0], A[1],…, A[n-1] (1)
Cần sắp xếp dãy theo thứ tự tăng dần:
A[0] ≤ A[1] ≤ … ≤ A[n-1] (2)
- GV đặt câu hỏi yêu cầu HS trả lời: Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.
Bước 2: HS thực hiện nhiệm vụ học tập:
- HS xem video và suy nghĩ câu trả lời.
- HS lắng nghe, suy nghĩ câu trả lời.
Bước 3: Báo cáo kết quả hoạt động, thảo luận:
- GV gọi đại diện một số HS trả lời.
- HS khác nhận xét, bổ sung.
Bước 4: Đánh giá kết quả thực hiện:
- GV nhận xét, đánh giá và kết luận.
[6.1.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.
2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).
1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]
- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Bài 21: Các thuật toán sắp xếp đơn giản.
B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Tìm hiểu về thuật toán sắp xếp chèn
a) Mục tiêu: Giúp HS hiểu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chèn.
b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được ý tưởng của thuật toán sắp xếp chèn.
c) Sản phẩm: HS nêu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chèn.
d) Tổ chức thực hiện:
| HOẠT ĐỘNG CỦA GV VÀ HS | SẢN PHẨM DỰ KIẾN | NLS |
Bước 1: GV chuyển giao nhiệm vụ: - GV đặt vấn đề theo Hoạt động 1 trang 99 SGK: Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn.
- GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp chèn (hình 21.1) cho HS quan sát.
- GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau: + So sánh số bước lặp với độ dài của dãy số ban đầu. + Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ số bước lặp? + Khi kết thúc lặp ta thu được kết quả gì? - Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp chèn. - GV giới thiệu cách mô tả thuật toán sắp xếp chèn trên thực tế. - GV đặt vấn đề: Trong hàm InsertionSort(A) có dòng A[j+1] = A[j], nghĩa là sao chép đè lên nhau. Tại sao không bị mất dữ liệu? - Dựa vào ví dụ vừa nêu ở Hoạt động 1, GV yêu cầu HS trả lời câu hỏi củng cố trang 100 SGK: + Câu 1: Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3]. + Câu 2: Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào? Bước 2: HS thực hiện nhiệm vụ học tập: - HS thảo luận nhóm, đọc SGK và trả lời câu hỏi. - HS sử dụng AI để tìm hiểu kiến thức: “Giải thích dòng lệnh A[j+1] = A[j] trong hàm InsertionSort(A). Tại sao phải lưu value = A[i] trước đó?” Bước 3: Báo cáo kết quả hoạt động, thảo luận: - Đại diện nhóm HS trình bày. *Câu hỏi củng cố trang 100 SGK: + Câu 1: Mô tả thuật toán sắp xếp chèn với dãy [5, 0, 4, 2, 3] có thể như sau: Bước 1. Chèn phần tử 0 vào trước 5, dãy thu được: [0, 5, 4, 2, 3] Bước 2. Chèn phần tử 4 vào trước 5, thu được: [0, 4, 5, 2, 3] Bước 3. Chèn phần tử 2 vào trước 4, thu được: [0, 2, 4, 5, 3]. Bước 4. Chèn phần tử 3 vào trước 4, thu được: [0, 2, 3, 4, 5]. + Câu 2: Nếu dãy ban đầu đã được sắp xếp đúng thì tại mỗi bước duyệt không cần thực hiện thao tác "chèn" nữa vì A[i] đã ở đúng vị trí rồi. Do vậy, thuật toán sắp xếp chèn sẽ không thực hiện bất cứ thao tác gì trên dãy đã cho. - Các nhóm khác nhận xét, bổ sung cho nhóm bạn. Bước 4: Đánh giá kết quả thực hiện: - GV nhận xét, đánh giá kết quả thảo luận của HS. | 1. Thuật toán sắp xếp chèn - Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt. - Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertSort(A) như sau: 1 deft InsertionSort(A): 2 n = len(A) 3 for i in range(1,n): 4 value = A[i] 5 j = i – 1 6 while j >= 0 and A[j] > value: 7 A[j+1] = A[j] 8 j = j – 1 9 A[j+1] = value | - 1.2.NC1a: HS phân tích được sự thay đổi của dữ liệu sau mỗi vòng lặp. - 6.1.NC1a: Xác định nhu cầu và giải quyết vấn đề kỹ thuật (Tư duy thuật toán). - 5.2.NC1a: Viết được hàm InsertionSort hoàn chỉnh. |
Hoạt động 2: Tìm hiểu về thuật toán sắp xếp chọn
a) Mục tiêu: Giúp HS hiểu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chọn.
b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được ý tưởng của thuật toán sắp xếp chọn.
c) Sản phẩm: HS nêu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chọn.
d) Tổ chức thực hiện:
…………………………………………..
…………………………………………..
…………………………………………..
Hoạt động 3: Tìm hiểu về thuật toán sắp xếp nổi bọt
a) Mục tiêu: Giúp HS hiểu được ý tưởng và các bước thực hiện của thuật toán sắp xếp nổi bọt.
b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được ý tưởng của thuật toán sắp xếp nổi bọt.
c) Sản phẩm: HS nêu được ý tưởng và các bước thực hiện của thuật toán sắp xếp nổi bọt.
d) Tổ chức thực hiện:
| HOẠT ĐỘNG CỦA GV VÀ HS | SẢN PHẨM DỰ KIẾN | NLS |
Bước 1: GV chuyển giao nhiệm vụ: - GV đặt vấn đề theo Hoạt động 3 trang 102 SGK: Cùng trao đổi, thảo luận về các ý tưởng của thuật toán sắp xếp nổi bọt. - GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp nổi bọt (hình 21.3) cho HS quan sát.
- GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau: + Nêu ý tưởng chính của thuật toán sắp xếp nổi bọt. - Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp nổi bọt. - GV đặt vấn đề: Nếu sau một vòng lặp mà không có cặp nào bị đổi chỗ, chứng tỏ dãy đã xếp xong. Làm sao để báo cho máy tính biết mà dừng lại sớm? - Dựa vào ví dụ vừa nêu ở Hoạt động 3, GV yêu cầu HS trả lời câu hỏi củng cố trang 103 SGK: + Câu 1: Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2]. + Câu 2: Khi nào thì các mũi tên ở tất cả các bước trong sơ đồ mô phỏng thuật toán sắp xếp nổi bọt đều có màu đỏ? Bước 2: HS thực hiện nhiệm vụ học tập: - HS thảo luận nhóm, đọc SGK và trả lời câu hỏi. - HS tư duy và thêm biến swapped = False. Trong vòng lặp j, nếu có đổi chỗ thì gán swapped = True. Cuối vòng lặp i, kiểm tra if not swapped: break. Hoặc sử dụng AI: “Hãy tối ưu hóa thuật toán Bubble Sort trong Python để nó tự động dừng lại nếu danh sách đã được sắp xếp. Giải thích vai trò của biến swapped.” Bước 3: Báo cáo kết quả hoạt động, thảo luận: - Đại diện nhóm HS trình bày. + Câu 1: Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2]. Pha 1. Duyệt một lượt từ trái sang phải, nấu hai phần tử cạnh nhau xếp không đúng thì đổi vị trí, cuối cùng thu được dãy [3, 1, 2, 4]. Pha 2. Làm lại tương tự bước trên, nhưng chỉ duyệt 3 phần tử, thu được dãy [1, 2, 3, 4]. Pha 3. Không cần đổi chỗ vì 1, 2 đã sắp xếp đúng vị trí. + Câu 2: Trong sơ đồ như hình 21.3 trong SGK, nếu dãy ban đầu sắp xếp theo thứ tự giảm dần thì ở tất cả các bước đều có màu đỏ trong sơ đồ. - Các nhóm khác nhận xét, bổ sung cho nhóm bạn. Bước 4: Đánh giá kết quả thực hiện: - GV nhận xét, đánh giá kết quả thảo luận của HS. - GV tổng kết kiến thức và yêu cầu HS ghi chép vào vở. | 3. Thuật toán sắp xếp nổi bọt - Thuật toán sắp xếp nổi bọt thực hiện nhiều vòng lặp, kiểm tra hai phần tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ. Có nhiều cách thể hiện thuật toán này, nhưng cách thường sử dụng hai vòng lặp lồng nhau, vòng lặp trong thực hiện thao tác đổi chỗ hai phần tử cạnh nhau cho đến khi dãy được sắp xếp xong. - Thuật toán sắp xếp nổi bọt được mô tả bằng hàm BubbleSort(A) như sau: 1 def BubbleSort(A): 2 n = len(A) 3 for i in range(n-1): 4 for j in range(n-1-i): 5 if A[j] > A[j+1]: 6 A[j],A[j+1]=A[j+1],A[j] | - 1.2.NC1a: HS phân tích được sự thay đổi của dữ liệu sau mỗi vòng lặp. - 6.1.NC1a: Xác định nhu cầu và giải quyết vấn đề kỹ thuật (Tư duy thuật toán). - 5.2.NC1a: Viết được hàm BubbleSort hoàn chỉnh. |
C. HOẠT ĐỘNG LUYỆN TẬP
a) Mục tiêu: HS củng cố kiến thức về các thuật toán sắp xếp đơn giản.
b) Nội dung: HS trả lời câu hỏi trắc nghiệm và hoàn thành bài tập phần Luyện tập trang 103 SGK.
c) Sản phẩm học tập: HS trả lời câu hỏi về các thuật toán sắp xếp đơn giản.
d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ:
- GV tổ chức trò chơi trắc nghiệm nhanh trên Quizizz hoặc Kahoot để củng cố toàn bài.
- GV cung cấp mã QR hoặc đường Links cho HS làm Phiếu bài tập, trả lời nhanh một số câu hỏi trắc nghiệm tổng kết bài học.
…………………………………………..
…………………………………………..
…………………………………………..
D. HOẠT ĐỘNG VẬN DỤNG
a) Mục tiêu: HS thực hiện làm bài tập Vận dụng để nắm vững kiến thức.
b) Nội dung: HS vận dụng kiến thức đã học và hiểu biết của bản thân để làm bài tập Vận dụng trang 103 SGK.
c) Sản phẩm: Câu trả lời nội dung Vận dụng.
d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ
- GV yêu cầu HS hoàn thành bài tập phần Vận dụng trang 103 SGK.
Bài 1. Viết lại các thuật toán sắp xếp trong bài theo thứ tự giảm dần.
Bài 2. Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học, chẳng hạn sắp xếp cac học sinh trong lớp theo chiều cao tăng dần.
Bước 2: HS thực hiện nhiệm vụ học tập
- HS tự tìm hiểu, đưa ra ý kiến.
- GV điều hành, quan sát, hỗ trợ.
Bước 3: Báo cáo kết quả hoạt động, thảo luận
- HS trình bày kết quả.
Kết quả:
Bài 1: Các thuật toán sẽ được viết lại như sau nếu muốn sắp xếp theo thứ tự giảm dần.
+ Sắp xếp chèn
1 deft InsertionSort(A):
2 n = len(A)
3 for i in range(1,n):
4 value = A[i]
5 j = i – 1
6 while j >= 0 and A[j] < value:
7 A[j+1] = A[j]
8 j = j – 1
9 A[j+1] = value
+ Sắp xếp chọn
1 def SelectionSort(A):
2 n = len(A)
3 for i in range(n-1):
4 iMax = i
5 for j in range(i+1,n):
6 if A[j] > A[iMax]:
7 iMax = j
8 A[i],A[iMax] = A[iMaxx],A[i]
+ Sắp xếp nổi bọt
1 def BubbleSort(A):
2 n = len(A)
3 for i in range(n-1):
4 for j in range(n-1-i):
5 if A[j] < A[j+1]:
6 A[j],A[j+1]=A[j+1],A[j]
Bài 2: Ý nghĩa thực tế có thể được hình dung như ví dụ sau: Giả sử HS lớp em được xếp theo một hàng dọc nhưng chưa được sắp xếp đúng theo thứ tự chiều cao tăng dần. Cô giáo sẽ nhắc nhở HS trong lớp sắp xếp lại. Sau đây là cách cô giáo nhắc nhở HS sắp xếp lại theo các thuật toán đã học.
+ Sắp xếp chèn. Cô giáo sẽ nhắc các bạn HS thực hiện công việc sau: hãy dời chỗ với bạn đứng trước em nếu bạn đó cao hơn em. Với cách này các bạn lần lượt thực hiện các thao tác đổi chỗ trên tương thích hoàn toàn với thuật toán sắp xếp chèn.
+ Sắp xếp chọn. GV sẽ tìm bạn thấp nhất lớp để thay đổi chỗ cho bạn đứng đầu hàng. Tiếp theo GV sẽ tìm HS thấp nhất trừ ra bạn đầu tiên, sau đó đổi chỗ bạn này với bạn thứ hai. Cứ làm như vậy cho đến bạn cuối cùng thì lớp sẽ sắp xếp xong.
+ Sắp xếp nổi bọt. Cô giáo nhắc các bạn HS thực hiện công việc sau: Tất cả các em nếu thấy bạn đứng trước cao hơn thì lập tức đổi chỗ cho bạn đó, cứ làm như vậy cho đến khi nào xếp xong thì thôi.
Bước 4: Đánh giá kết quả thực hiện
- GV nhận xét, đánh giá, đưa ra một vài ý mà HS còn thiếu, chốt đáp án.
- GV tổng kết tiết học.
[5.2.NC1a: HS viết chương trình máy tính để thực hiện yêu cầu.
1.2.NC1a: Tổ chức dữ liệu thành mảng, truy cập vào dữ liệu để lấy thông tin.
6.1.NC1a: Xác định nhu cầu và giải quyết vấn đề kỹ thuật.]
* HƯỚNG DẪN VỀ NHÀ
- Ghi nhớ kiến thức trong bài.
- Hoàn thành các bài tập trong SBT.
- Chuẩn bị bài mới Bài 22 – Thực hành bài toán sắp xếp.
=> Giáo án Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản