Giáo án và PPT Tin học 7 chân trời Bài 14: Thuật toán sắp xếp

BÀI 14: THUẬT TOÁN SẮP XẾP

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS hoạt động cặp đôi và nêu nhiệm vụ: Có 4 tấm thẻ, mỗi thẻ ghi một số và xếp thành một dãy dọc trên mặt bàn từ trên xuống dưới như Hình 1. Em hãy trao đổi với bạn để chỉ ra cách sắp xếp dãy thẻ theo thứ tự giá trị tăng dần của số ghi trên thẻ, với điều kiện chỉ có thể di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liệt kê.

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

1. THUẬT TOÁN SẮP XẾP NỔI BỌT

Hoạt động 1: Thuật toán sắp xếp nổi bọt

GV tổ chức cho HS theo luận cặp đôi và trả lời câu hỏi:

+Em hãy nêu một số ví dụ về bài toán sắp xếp trong thực tiễn.

+ Từ nội dung mục 1. Thuật toán sắp xếp nổi bọt và hoạt động thực hành sắp xếp, em hãy mô tả thuật toán sắp xếp nổi bọt.

Sản phẩm dự kiến:

- Thuật toán sắp xếp nổi bọt: thực hiện lặp đi lặp lại việc đổi chỗ 2 số liền kề trong một dãy số nếu chúng đứng sai thứ tự.

- Mô tả thuật toán sắp xếp nổi bọt:

          + Đầu vào: Dãy chưa được sắp xếp

          + Đầu ra: Dãy được sắp xếp không giảm

(1) Chuyển phần tử nhỏ nhất về vị trí đầu tiên

          (1.1) So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử đầu tiên

          (1.2) Nếu nhỏ hơn thì đổi chỗ hai phần tử

          (1.3) Kết thúc vòng lặp, phần tử nhỏ nhất “nổi lên” vị trí đầu tiên của dãy

(2) Chuyển phần tử nhỏ thứ hai về vị trí thứ hai

          (2.1) So sánh từng phần tử của dãy với phần tử liền trước, lần lượt từ phần tử cuối cùng lên phần tử thứ hai

          (2.2) Nếu nhỏ hơn thì đổi chỗ hai phần tử

          (2.3) Kết thúc vòng, phần tử nhỏ thứ hai “nổi lên” vị trí thứ hai của dãy

(3) Thực hiện tương tự như trên với phần tử nhỏ thứ ba, thứ tư,… cho đến phần tử liền trước phần tử cuối cùng

(4) Kết thúc thuật toán, ta sẽ nhận được dãy số đã được sắp xếp theo thứ tự không giảm

2. THUẬT TOÁN SẮP XẾP CHỌN

Hoạt động 2: Thuật toán sắp xếp chọn

- GV yêu cầu HS hoạt động cá nhóm, quan sát Hình 6 – 10 và các hình liên quan, đọc nội dung mục 2. Thuật toán sắp xếp chọn SGK tr.79 – 82 và trả lời câu hỏi:

+ Từ nội dung mục 2. Thuật toán sắp xếp chọn và hoạt động thực hành sắp xếp, em hãy mô tả các bước thuật toán sắp xếp chọn.

+ Em có nhận xét gì về số bước thực hiện ở mỗi vòng lặp của hai thuật toán sắp xếp vừa học (nhất là trong trường hợp số phần tử của dãy cần sắp xếp đủ lớn)? Vì sao?

+ Thuật toán này có thực hiện chia một bài toán thành những bài toán nhỏ hơn không? Vì sao?

Sản phẩm dự kiến:

- Thực hiện chọn phần tử nhỏ nhất trong dãy chưa được sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy chưa được sắp xếp

- Lặp lại quá trình này cho đến khi dãy chưa sắp xếp chỉ còn một phần tử

- Mô phỏng lại thuật toán sắp xếp chọn:

          + Bước 1. Coi số đầu tiên của dãy số (vị trí 1) là số nhỏ nhất (MIN).

          + Bước 2. So sánh MIN với số thứ 2

          + Bước 3. So sánh MIN với số thứ 3

          + Bước 4. So sánh MIN với số thứ 4

=> Với thuật toán sắp xếp chọn, bài toán sắp xếp dãy số ban đầu cũng được chia thành những bài toán nhỏ để giải quyết. Các bài toán nhỏ là di chuyển số nhỏ nhất (hoặc lớn nhất) về vị trí đầu tiên của dãy chưa sắp xếp. Phạm vi của dãy chưa sắp xếp hẹp dần sau mỗi lần lặp

HOẠT ĐỘNG LUYỆN TẬP

Từ nội dung bài học, GV yêu cầu HS hoàn thành các bài tập trắc nghiệm sau:

Câu 1: Đặc điểm của thuật toán sắp xếp nổi bọt là:

A. Lặp lại quá trình chọn phần tử nhỏ nhất đưa về vị trí đầu tiên.

B. Lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự.

C. Lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nhau.

D. Lặp đi lặp lại việc đổi chỗ 2 phần tử đối xứng nhau.

Câu 2: Đặc điểm của thuật toán sắp xếp chọn là:

A. Lặp lại quá trình chọn phần tử nhỏ nhất (hoặc lớn nhất) trong dãy chưa sắp xếp và đưa phần tử này về vị trí đầu tiên của dãy đó.

B. Lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nếu chúng sai thứ tự.

C. Lặp đi lặp lại việc đổi chỗ 2 phần tử liền kề nhau.

D. Lặp đi lặp lại việc đổi chỗ 2 phần tử đối xứng nhau.

Câu 3: Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?

A. Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.

B. Lặp lại quá trình chọn số nhỏ nhất trong dãy chưa sắp xếp và đưa số này về vị trí đầu tiên.

C. Đổi chỗ 2 số liền kề nhau liên tục đến khi dãy số được sắp xếp.

D. So sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm.

Câu 4: Cho dãy số xếp từ trái qua phải là; 20, 21, 17, 19. Cho biết với thuật toán sắp xếp chọn ở vòng lặp số 2 thì số nhỏ nhất được tìm thấy là số nào?

A. 20

B. 21

C. 17

D. 19

Câu 5: Bài toán: Em hãy thực hiện sắp xếp các bạn trong tổ em theo thứ tự chiều cao không giảm. Với bài toán này em có thể sử dụng thuật toán sắp xếp nào?

A. Chỉ có thể sử dụng thuật toán sắp xếp nổi bọt

B. Chỉ có thể sử dụng thuật toán sắp xếp chọn

C. Có thể sử dụng thuật toán sắp xếp nổi bọt hoặc chọn

D. Không thể sử dụng hai thuật toán sắp xếp nổi bọt hoặc chọn

Sản phẩm dự kiến:

HOẠT ĐỘNG VẬN DỤNG

Vận dụng kiến thức, GV yêu cầu HS trả lời câu hỏi:

Câu 1: Liệt kê các vòng lặp của thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chọn để sắp xếp các dãy sau theo thứ tự tăng dần:

a) Dãy số: 9, 6, 11, 3, 7.

b) Dãy số: H, D, A, B, Y.

Câu 2: Chỉ ra phương án sai.

Ý nghĩa của việc chia bài toán thành bài toán nhỏ hơn là:

A. Giúp công việc đơn giản hơn.

B. Giúp công việc dễ giải quyết hơn.

C. Làm cho công việc trở nên phức tạp hơn.

D. Giúp bài toán trở nên dễ hiểu hơn.