Video giảng Tin học 7 chân trời bài 14 Thuật toán sắp xếp

Tóm lược nội dung

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

Xin chào các em học sinh thân mến, chúng ta lại gặp nhau trong bài học ngày hôm nay rồi!

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• Giải thích được thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chọn.
• Biểu diễn và mô phỏng được thuật toán sắp xếp trên bộ dữ liệ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.

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

Trước khi bước vào bài học ngày hôm nay, các em suy nghĩ để trả lời tình huống này cho cô: 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 KHÁM PHÁ

Nội dung 1: Thuật toán sắp xếp nổi bọt

+ 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.

Video trình bày nội dung:

- 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.

Nội dung 2: 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?

+ Theo em, 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?

Video trình bày nội dung:

- 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.

………..

Nội dung video Bài 14: Thuật toán sắp xếp còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.