Tải giáo án Powerpoint Tin học 7 CTST bài 14: Thuật toán sắp xếp (3 tiết)

NHIỆT LIỆT CHÀO ĐÓN CÁC EM ĐẾN VỚI BÀI HỌC HÔM NAY!

KHỞI ĐỘNG

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ền kề.

Gợi ý: HS vừa làm vừa nêu các bước thực hiện:

• Bắt đầu từ cặp thẻ số nào?
• Khi nào thì đổi chỗ hai thẻ số đó?
• Chọn cặp số nào tiếp theo?
• Kết quả của việc thực hiện sẽ như thế nào?

BÀI 14: THUẬT TOÁN SẮP XẾP (3 Tiết)

NỘI DUNG BÀI HỌC

Thuật toán sắp xếp nổi bọt

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

Em hiểu thế nào là 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 sắp xếp dãy phần tử (không tăng hay không giảm) bằng cách thực hiện 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ự.

Với thuật toán sắp xếp nổi bọt, bài toán sắp xếp dãy số ban đầu được chia thành những bài toán nhỏ để giải quyết. Việc chia bài toàn thành những bài toán nhỏ hơn giúp công việc trở nên đơn giản, dễ giải quyết hơn.

Từ thông tin SGK 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 cho bài toán sắp xếp dãy tổng quát.

Mô phỏng thuật toán sắp xếp nổi bọt

(áp dụng cho bài toán sắp xếp dãy tổng quá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.
• Chuyển phần tử nhỏ nhất về vị trí đầu tiên.
• 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.
• 2 Nếu nhỏ hơn thì đổi chỗ hai phần tử.
• 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.
• Chuyển phần tử nhỏ thứ hai về vị trí thứ hai.
• 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 Nếu nhỏ hơn thì đổi chỗ hai phần tử.
• 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.
• 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.
• 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.
• Em hãy sắp xếp dãy chữ cái ở Hình 5 theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt (mô phỏng quá trình thực hiện bằng hình vẽ tương tự như các Hình 2, 3, 4). Quy ước, trong bảng chữ cái, chữ đứng trước “nhỏ hơn” chữ đứng sau.

2. Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy số không giảm bằng cách nào dưới đây?
3. Đổ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.
4. Di chuyển số nhỏ nhất về cuối dãy số.
5. Di chuyển số lớn nhất về đầu dãy số.
6. Thuật toán sắp xếp chọn

Dựa vào thông tin SGK và cho biết: Em hiểu thế nào là thuật toán sắp xếp chọn?

Thuật toán sắp xếp chọn thực hiện sắp xếp dãy phần tử không giảm (hoặc không tăng) bằng cách lặp đi 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 đó.

• Đầu vào: Dãy thẻ ghi các số xếp từ trái qua phải là 20, 21, 17, 19.
• Đầu ra: Dãy thẻ ghi các số được sắp xếp tăng dần là 17, 19, 20, 21.

Lưu ý

Để tìm số nhỏ nhất trong dãy số, ví dụ dãy 20, 21, 17, 19, ta thực hiện như sau:

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