KHỞI ĐỘNG
Có một bó que tính dài ngắn khác nhau, em hãy xếp các que tính thành dãy từ trái sang phải theo thứ tự ngắn dần.
Câu trả lời:
HS tự thực hiện.
2. Thuật toán sắp xếp chọn
Câu hỏi: Bài toán sắp xếp ở mục 1 trên đây có gì giống và khác với bài toán sắp xếp nêu ở phần khởi động? Ý tưởng sắp xếp ở mục 1 có gì giống và khác với ý tưởng sắp xếp em đã sử dụng ở phần khởi động?
Câu trả lời:
Điểm giống và khác của bài toán ở mục 1 với bài toán sắp xếp nêu ở phần khởi động là:
- Giống: đều sắp xếp theo thứ tự giảm dẩn.
- Khác:
- Bài toán ở phần khởi động không có ý tưởng sắp xếp bằng cách chọn dần mà chỉ sắp xếp để phù hợp với yêu cầu của đề bài.
- Bài toán ở mục 1 là sắp xếp theo các bước, đổi chỗ các số cho nhau để được kết quả phù hợp.
Điểm giống và khác của ý tưởng sắp xếp ở mục 1 với ý tưởng sắp xếp em đã sử dụng ở phần khởi động là:
- Giống: đều đặt những que tính dài trước giống như chọn ra số lớn nhất ở bài toán mục 1.
- Khác:
- Bài toán ở phần khởi động: chỉ cần sắp xếp để được các que tính thành dãy theo thứ tự ngắn dần.
- Bài toán ở mục 1: đổi chỗ các số hạng để được dãy có thứ tự giảm dần.
LUYỆN TẬP
Trình bày diễn biến từng bước của thuật toán sắp xếp chọn cho dãy số 11, 70, 18, 39, 63, 52, 41, 5 theo mẫu ở Hình 1.
Câu trả lời:
Diễn biến từng bước của thuật toán sắp xếp chọn cho dãy số 11, 70, 18, 39, 63, 52, 41, 5 theo mẫu ở Hình 1.
- Bước 1: Số lớn nhất trong dãy số (70) cần đươc chuyển về vị trí thứ nhất trong dãy, do đó đổi chỗ 70 với 11. Sau bước này, vì 70 đã ở đúng vị trí mong muốn nên tiếp theo chỉ cần quan tâm đến dãy số còn lại: 11, 18, 39, 63, 52, 41, 5.
- Bước 2: Số lớn nhất trong dãy số còn lại (63) cần đươc chuyển về vị trí đầu dãy này, do đó đổi chỗ 63 với 11. Sau bước này, có thêm số 63 đã ở đúng vị trí mong muốn, dãy số còn lại chưa được sắp xếp là: 18, 39, 11, 52, 41, 5.
- Bước 3: Số lớn nhất trong dãy số còn lại (52) cần đươc chuyển về vị trí đầu dãy này, do đó đổi chỗ 52 với 18. Sau bước này, có thêm số 52 đã ở đúng vị trí mong muốn, dãy số còn lại chưa được sắp xếp là: 39, 11, 18, 41, 5.
- Bước 4: Số lớn nhất trong dãy số còn lại (41) cần đươc chuyển về vị trí đầu dãy này, do đó đổi chỗ 41 với 39. Sau bước này, có thêm số 41 đã ở đúng vị trí mong muốn, dãy số còn lại chưa được sắp xếp là: 11, 18, 39, 5.
- Bước 5: Số lớn nhất trong dãy số còn lại (39) cần đươc chuyển về vị trí đầu dãy này, do đó đổi chỗ 39 với 11. Sau bước này, có thêm số 39 đã ở đúng vị trí mong muốn, dãy số còn lại chưa được sắp xếp là: 18, 11, 5.
- Bước 6: Vì số lớn nhất trong dãy số còn lại (18) đã ở đúng vị trí của nó, nên không cần đổi chỗ dãy số còn lại này. Dãy số còn lại chưa được sắp xếp là 11,5.
- Bước 7: tương tự bước 6, ta có dãy kết quả là: 70, 63, 52, 41, 39, 18, 11, 5.
VẬN DỤNG
Trong thuật toán sắp xếp chọn:
1) Khi nào không cần thực hiện thao tác "Đổi chỗ am và a1 cho nhau" mà kết quả sắp xếp vẫn đúng?
2) Nếu thay "Tìm giá trị lớn nhất" bằng "Tìm giá trị nhỏ nhất" thì kết quả nhận được là dãy số có thứ tự ra sao?
Câu trả lời:
Trong thuật toán sắp xếp chọn:
1) Không cần thực hiện thao tác "Đổi chỗ am và a1 cho nhau" mà kết quả sắp xếp vẫn đúng khi am đã là số lớn nhất cần tìm của một dãy số.
2) Nếu thay "Tìm giá trị lớn nhất" bằng "Tìm giá trị nhỏ nhất" thì kết quả nhận được là dãy số có thứ tự tăng dần.
TỰ KIỂM TRA
Câu 1. Hãy nêu vài ví dụ bài toán sắp xếp trong thực tế và nói rõ tiêu chí sắp xếp.
Câu 2. Hãy tóm tắt bằng một câu trả lời cho câu hỏi: Thế nào là sắp xếp chọn?
Câu trả lời:
Câu 1. Ví dụ bài toán sắp xếp trong thực tế và nói rõ tiêu chí sắp xếp.
- Sắp xếp danh sách kết quả điểm trung bình học kì 2 của lớp 7A theo thứ tự giảm dần. Tiêu chí sắp xếp là điểm trung bình kì 2 theo thứ tự giảm dần.
- Sắp xếp danh sách kết quả thi môn Thể dục của lớp 7B theo thứ tự tăng dần. Tiêu chí sắp xếp là kết quả thi môn Thể dục theo thứ tự tăng dần.
Câu 2. Sắp xếp chọn là chọn phần tử lớn nhất trong dãy chưa sắp xếp còn lại và xếp vào đầu dãy đó.