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

PHẦN I. HỆ THỐNG CÂU HỎI, BÀI TẬP TRONG SGK

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 đổ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ề.

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

Làm 1: 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.

Làm 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?

1. Đổi chỗ 2 số liền kề nhau chúng đứng sai thứ tự cho đến khi dãy số được sắp xếp.
2. Di chuyển số nhỏ nhất về cuối danh sách.
3. Di chuyển số nhỏ nhất về đầu danh sách.

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

Làm 1: Em hãy sắp xếp dãy chữ cái ở Hình 5 theo hàng ngang rồi sử dụng thuật toán sắp xếp chọn (mô phỏng quá trình thực hiện bằng hình vẽ như các Hình 7, 8, 9) thực hiện sắp xếp dãy theo thứ tư tăng dần.

Làm 2: Thuật toán sắp xếp chọn thực hiện sắp xếp dãy số tăng dần bằng cách nào dưới đây?

1. Đổ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.
2. 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ủa dãy đó.

LUYỆN TẬP

Luyện tập 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.

1. Dãy số: 9, 6, 11, 3, 7
2. Dãy chữ cái: H, D, A, B, Y.

Luyện tập 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à:

1. Giúp công việc đơn giản hơn.
2. Giúp công việc dễ giải quyết hơn.
3. Làm cho công việc trở nên phức tạp.
4. Giúp bài toán trở nên dễ hiểu hơn.

VẬN DỤNG

Sử dụng một thuật toán đã học để 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 (ghi chiều cao của các bạn theo cùng đơn vị đo là cm vào bảng theo mẫu Bảng 1 dưới đây).

PHẦN II. 5 PHÚT TRẢ LỜI CÂU HỎI, BÀI TẬP SGK

KHỞI ĐỘNG

Đáp án KD: 

• Gợi ý: Di chuyển thẻ số 15 và số 18, di chuyển thẻ 19 và 16. Di chuyển thẻ 19 và 15, đổi chỗ thẻ 15 và 16, đổi chỗ thẻ 18 và 19.
• Kết quả: thu được dãy thẻ sắp xếp theo thứ tự tăng dần.

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

Đáp án L1: 

Đáp án L2: A

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

Đáp án L1: 

Đáp án L2: B

LUYỆN TẬP

Đáp án LT1: 

a) 

• Thuật toán nổi bọt:

Dãy số ban đầu: 9, 6, 11, 3, 7

Vòng lặp 1: 9, 6, 3, 11, 7 ® 9, 3, 6, 11, 7 ® 3, 9, 6, 11, 7

Vòng lặp 2: 3, 6, 9, 11, 7

Vòng lặp 3: 3, 6, 9, 7, 11 ® 3, 6, 7, 9, 11

Dãy thẻ số đã được sắp xếp: 3, 6, 7, 9, 11

• Thuật toán sắp xếp: 

Vòng lặp 1: 3, 6, 9, 11, 7

Vòng lặp 2: 3, 6, 7, 11, 9

Vòng lặp 3: 3, 6, 7, 9, 11

Dãy thẻ số đã được sắp xếp: 3, 6, 7, 9, 11

b) 

• Thuật toán nổi bọt:

Dãy số ban đầu: H, D, A, B, Y.

Vòng lặp 1: H, A, D, B, Y => A, H, D, B, Y

Vòng lặp 2: A, H, B, D, Y => A, B, H, D, Y

Vòng lặp 3: A, B, D, H, Y

Dãy thẻ số đã được sắp xếp: A, B, D, H, Y

• Các vòng lặp của thuật toán sắp xếp:

Vòng lặp 1: A, D, H, B, Y

Vòng lặp 2: A, B, H, D, Y

Vòng lặp 3: A, B, D, H, Y

Dãy thẻ số đã được sắp xếp: A, B, D, H, Y

Đáp án LT2: C

VẬN DỤNG

Đáp án VD:

HS tự thực hiện.