Giáo án Tin học 7 Kết nối tri thức Chủ đề 5 Bài 16 Thuật toán sắp xếp

Bài 16. Thuật toán sắp xếp
Môn học: Tin Học; Lớp: 7
Thời gian thực hiện: 3 tiết I. MỤC TIÊU
1. Kiến thức:
- Giải thích được một vài thuật toán sắp xếp cơ bản.
- Biểu diễn và mô phỏng được hoạt động của thuật toán sắp xếp với bộ dữ liệu đầu vào có kích thước nhỏ.
- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.
2. Năng lực:
- Năng lực tự chủ và tự học
- Năng lực giao tiếp và hợp tác
- Năng lực sáng tạo và giải quyết vấn đề
3. Phẩm chất:
- Nghiêm túc, tập trung, tích cực chủ động.
- Rèn luyện phẩm chất chăm học, chăm làm.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU 1. Giáo viên
- Chuẩn bị bài giảng, máy chiếu. - Sách giáo khoa. 2. Học sinh - Sách giáo khoa, vở ghi. - Kiến thức đã học.
III. TIẾN TRÌNH DẠY HỌC
1. HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU)
a) Mục tiêu: Tạo hứng thú học tập cho học sinh
b) Nội dung: HS thảo luận để trả lời câu hỏi


c) Sản phẩm: Câu trả lời của nhóm.
d) Tổ chức thực hiện:
- GV giới thiệu mục đích, yêu cầu và chia nhóm HS thảo luận: Dựa trên Hình 16.1,
HS thảo luận để giải thích cách thực hiện.
Có hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai
chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho
cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện
công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì.
Em hãy quan sát Hình 16.1b, Hình 16.1c, Hình 16.1d để biết cách thức hiện.
- Kết thúc hoạt động, HS báo cáo kết quả thảo luận.
- GV nhận xét, đánh giá kết quả.
2. HÌNH THÀNH KIẾN THỨC MỚI
Hoạt động 1: Tìm hiểu thuật toán sắp xếp nổi bọt
a) Mục tiêu: Biểu diễn và mô phỏng được hoạt động của thuật toán sắp xếp
nổi bọt với bộ dữ liệu đầu vào có kích thước nhỏ.
b) Nội dung: HS thảo luận nhóm để tìm hiểu nội dung kiến thức theo yêu cầu của GV
c) Sản phẩm: Kết quả hoạt động nhóm.
d) Tổ chức thực hiện:


Hoạt động của GV và
Sản phẩm dự kiến HS
1. THUẬT TOÁN SẮP XẾP NỔI BỌT
* Bước 1: Chuyển giao
- Ví dụ: Sắp xếp dãy các số 4, 2, 3, 1 theo chiều tăng nhiệm vụ: dần
GV: Tổ chức các hoạt
- Ý tưởng: Sử dụng thuật toán sắp xếp nổi bọt như sau: động
+ Xét từng vị trí từ đầu đến cuối dãy.
- GV yêu cầu HS đọc hiểu
+ Tại mỗi vị trí được xét, thuật toán tìm phần tử nhỏ và cùng với HS diễn giải
nhất trong những phần tử phía sau để đưa vào vị trí đó. hoạt động của thuật toán
Việc này được thực hiện bằng một vòng lặp, so sánh sắp xếp nổi bọt với 4 giá
từng cặp phần tử cạnh nhau và hoán đổi chúng nếu số ở trị qua hình minh họa phía sau nhỏ hơn. trong SGK. - Minh họa: - GV yêu cầu các nhóm thảo luận và hoàn thành nhiệm vụ sau:
Em hãy thực hiện thuật
toán sắp xếp nổi bọt để
sắp xếp 5 số sau đây theo
thứ tự tăng dần. Hãy mô
phỏng các bước sắp xếp
bằng hình vẽ minh họa
tương tự như hình 16.2, hình 16.3, hình 16.4 3 5 4 1 2


Hoạt động của GV và
Sản phẩm dự kiến HS
HS: Thảo luận, trả lời - GV yêu cầu HS trả lời câu hỏi củng cố:
1. Thuật toán sắp xếp nổi
bọt sắp xếp danh sách bằng cách:
A. Chọn phần tử có giá trị
bé nhất đặt vào đầu danh sách.
B. Chọn phần tử có giá trị
lớn nhất đặt vào đầu danh sách.
C. Hoán đổi nhiều lần các
phần tử liền kề nếu giá trị
của chúng không đúng thứ tự.
- Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự D. Chèn phần tử vào vị trí nhiên:
thích hợp để đảm bảo
1. Với phần tử đầu tiên, thực hiện vòng lặp như sau:
danh sách sắp xếp theo
1.1. So sánh 2 phần tử đứng cạnh nhau theo thứ tự từ đúng thứ tự.
cuối dãy lên phần tử đầu tiên.
* Bước 2: Thực hiện
1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước nhiệm vụ:
thì đổi chỗ chúng cho nhau. + HS: Suy nghĩ, thảo
1.3. Cuối vòng lặp sẽ nhận được dãy số với phần tử nhỏ luận, trả lời câu hỏi
nhất nổi lên vị trí đầu tiên. + GV: Quan sát và hỗ trợ