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?
Đổ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.
Di chuyển số nhỏ nhất về cuối danh sách.
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?
Đổ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.
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.
Dãy số: 9, 6, 11, 3, 7
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à:
Giúp công việc đơn giản hơn.
Giúp công việc dễ giải quyết hơn.
Làm cho công việc trở nên phức tạp.
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 .Lời giải tham khảo
KHỞI ĐỘNG
Để sắp xếp dãy thẻ theo thứ tự giá trị tăng dần, ta cần di chuyển các thẻ bằng cách đổi chỗ các cặp thẻ liền kề. Quá trình này có thể được thực hiện bằng cách áp dụng thuật toán sắp xếp nổi bọt (Bubble Sort).
Ví dụ: Giả sử các tấm thẻ có giá trị là 4, 2, 3, 1, ta sẽ thực hiện như sau:
Lượt 1: So sánh từng cặp thẻ liền kề, đổi chỗ nếu cần thiết:
So sánh thẻ 4 và 2, đổi chỗ (2, 4, 3, 1).
So sánh thẻ 4 và 3, đổi chỗ (2, 3, 4, 1).
So sánh thẻ 4 và 1, đổi chỗ (2, 3, 1, 4).
Lượt 2: Lặp lại quá trình với dãy mới:
So sánh thẻ 2 và 3, không đổi chỗ (2, 3, 1, 4).
So sánh thẻ 3 và 1, đổi chỗ (2, 1, 3, 4).
Lượt 3: Tiếp tục lặp lại:So sánh thẻ 2 và 1, đổi chỗ (1, 2, 3, 4).
Kết quả cuối cùng: 1, 2, 3, 4.
1. THUẬT TOÁN SẮP XẾP NỔI BỌT
Làm 1: Để sắp xếp dãy chữ cái theo thứ tự tăng dần (quy ước: chữ đứng trước nhỏ hơn chữ đứng sau), áp dụng thuật toán sắp xếp nổi bọt:
Dãy ban đầu: E, B, D, A, C
Lượt 1:So sánh E và B, đổi chỗ: B, E, D, A, C.
So sánh E và D, đổi chỗ: B, D, E, A, C.
So sánh E và A, đổi chỗ: B, D, A, E, C.
So sánh E và C, đổi chỗ: B, D, A, C, E.
Lượt 2:So sánh B và D, không đổi chỗ: B, D, A, C, E.
So sánh D và A, đổi chỗ: B, A, D, C, E.So sánh D và C, đổi chỗ:
B, A, C, D, E.
Lượt 3:So sánh B và A, đổi chỗ:
A, B, C, D, E.
Kết quả: A, B, C, D, E.
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:
Đổi chỗ 2 số liền kề nhau nếu chúng đứng sai thứ tự, lặp lại cho đến khi dãy số được sắp xếp.
2. THUẬT TOÁN SẮP XẾP CHỌN
Làm 1: Để sắp xếp dãy chữ cái theo thứ tự tăng dần bằng thuật toán sắp xếp chọn:
Dãy ban đầu: E, B, D, A, C
Lượt 1: Tìm chữ cái nhỏ nhất trong dãy (A) và đưa về vị trí đầu tiên:
A, B, D, E, C.
Lượt 2: Tìm chữ cái nhỏ nhất trong dãy còn lại (B) và giữ nguyên:
A, B, D, E, C.
Lượt 3: Tìm chữ cái nhỏ nhất trong dãy còn lại (C) và đổi chỗ với D:
A, B, C, E, D.
Lượt 4: Tìm chữ cái nhỏ nhất trong dãy còn lại (D) và đổi chỗ với E:
A, B, C, D, E.
Kết quả: A, B, C, D, E.
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:
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: Sắp xếp dãy số: 9, 6, 11, 3, 7 bằng hai thuật toán:
Sắp xếp nổi bọt (Bubble Sort):
Lượt 1: 6, 9, 3, 7, 11.
Lượt 2: 6, 3, 7, 9, 11.
Lượt 3: 3, 6, 7, 9, 11.
Lượt 4: 3, 6, 7, 9, 11 (dãy đã sắp xếp).
Sắp xếp chọn (Selection Sort):
Lượt 1: Chọn số nhỏ nhất (3) và đưa về đầu dãy: 3, 6, 11, 9, 7.
Lượt 2: Chọn số nhỏ nhất trong dãy còn lại (6) và giữ nguyên: 3, 6, 11, 9, 7.
Lượt 3: Chọn số nhỏ nhất trong dãy còn lại (7) và đổi chỗ với 11: 3, 6, 7, 9, 11.
Lượt 4: Chọn số nhỏ nhất trong dãy còn lại (9) và giữ nguyên: 3, 6, 7, 9, 11.
Kết quả: 3, 6, 7, 9, 11.
Sắp xếp dãy chữ cái: H, D, A, B, Y bằng hai thuật toán:
Sắp xếp nổi bọt:
Lượt 1: D, A, B, H, Y.
Lượt 2: A, B, D, H, Y.
Lượt 3: A, B, D, H, Y (dãy đã sắp xếp).
Sắp xếp chọn:
Lượt 1: Chọn chữ nhỏ nhất (A) và đưa về đầu dãy: A, D, H, B, Y.
Lượt 2: Chọn chữ nhỏ nhất trong dãy còn lại (B) và đổi chỗ với D: A, B, H, D, Y.
Lượt 3: Chọn chữ nhỏ nhất trong dãy còn lại (D) và đổi chỗ với H: A, B, D, H, Y.
Lượt 4: Chọn chữ nhỏ nhất trong dãy còn lại (H) và giữ nguyên: A, B, D, H, Y.
Kết quả: A, B, D, H, Y.
Luyện tập 2: Phương án sai là: "Làm cho công việc trở nên phức tạp". Việc chia bài toán thành bài toán nhỏ giúp công việc dễ giải quyết hơn, đơn giản hơn và dễ hiểu hơn.
VẬN DỤNG
Để sắp xếp các bạn trong tổ theo chiều cao không giảm, ta làm như sau:
Đo chiều cao của từng bạn trong tổ (ví dụ: 150 cm, 155 cm, 148 cm, 160 cm).
Áp dụng một thuật toán sắp xếp (ví dụ, sắp xếp nổi bọt hoặc sắp xếp chọn):
Sử dụng sắp xếp nổi bọt:
Lượt 1: So sánh và đổi chỗ nếu cần: 148, 150, 155, 160.
