Giáo án điện tử tin học 7 cánh diều bài 3: Sắp xếp chọn

CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

               Có một bó que tính dài ngắn khác nhau, em hãy sắp xếp các que tính thành dãy từ trái sang phải theo thứ tự ngắn dần.

Gợi ý:

• Bước 1: Que tính dài nhất cần được chuyển về vị trí thứ nhất trong dãy.
• Bước 2: Que tính dài nhất trong dãy còn lại cần được chuyển về đầu dãy này.

Tiếp tục lặp lại việc “Chọn lấy que dài nhất trong dãy và đổi chỗ nó với các que còn lại” cho đến khi hết dãy.

BÀI 3: SẮP XẾP CHỌN

NỘI DUNG BÀI HỌC

Ý tưởng sắp xếp bằng cách chọn dần

Thuật toán sắp xếp chọn

Bài toán sắp xếp

1. Ý tưởng sắp xếp bằng cách chọn dần

Xét bài toán sắp xếp:

Em hãy đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để tạo ra được dãy có thứ tự giảm dần.

Em hãy đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để tạo ra được dãy có thứ tự giảm dần.

Video sau đây hướng dẫn sắp xếp số hạng trong dãy số bằng cách chọn dần.

2. Thuật toán sắp xếp chọn

HS thảo luận nhóm đôi, trả lời các câu hỏi phần Hoạt động SGK tr.84:

• Bài toán sắp xếp ở mục 1 trên đây có gì giống và khác với bài toán sắp xếp nêu ở phần khởi động?
• Ý tưởng sắp xếp ở mục 1 có gì giống và khác với ý tưởng sắp xếp em đã sử dụng ở phần khởi động?

Đọc thông tin trong mục 2, quan sát hình 2, hình 3 SGK tr.85, trả lời các câu hỏi sau:

• Mô tả thuật toán sắp xếp chọn.
• Nêu các bước để tìm được số lớn nhất của một dãy nằm ở vị trí nào.

KẾT LUẬN

Bài toán sắp xếp đặt ra như sau:

• Đầu vào: Dãy số a₁, a₂, …, a_n gọi là dãy (a).
• Đầu ra: Dãy số a’₁, a’₂, …, a’_n gồm các số của dãy (a) nhưng thứ tự giảm dần.
• Mô tả thuật toán sắp xếp chọn:

Lặp với i từ 1 đến n - 1:

1. Tìm số lớn nhất trong dãy số a_i, a_i+1, ..., a_n gọi là a_m
2. Đổi chỗ a_m và a_i cho nhau

Hết lặp

• Bước 1: Tạm ghi nhận vị trí của số lớn nhất là 1
• Bước 2: So sánh a₂ với số lớn nhất, nếu a₂ lớn hơn số lớn nhất thì ghi nhận lại vị trí số lớn nhất là 2.
• Cứ tiếp tục như vậy, đến khi so sánh xong a_n với số lớn nhất và ghi nhận lại vị trí của số lớn nhất (nếu cần) thì số lớn nhất chính là số lớn nhất trong toàn bộ dãy và ta đã tìm được vị trí m của số lớn nhất trong dãy.

3. Bài toán sắp xếp

Đọc thông tin mục 3 trong SGK và trả lời câu hỏi:

• Cho biết những nội dung cần xác định khi phát biểu bài toán sắp xếp.
• Lấy ví dụ về một bài toán sắp xếp; chỉ rõ dãy đầu vào và tiêu chí sắp xếp của bài toán đó.

KẾT LUẬN

                Sắp xếp là bài toán cơ sở của tin học. Duy trì dữ liệu được sắp xếp đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu.

Sắp xếp là bài toán cơ sở của tin học. Duy trì dữ liệu được sắp xếp đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu.