Giải Tin Học 7 trang 81
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 81–82
Nội dung chính
Hai trang này trình bày lý thuyết về Thuật toán sắp xếp nổi bọt và Thuật toán sắp xếp chọn, kèm theo một hoạt động thực hành và một câu hỏi trắc nghiệm.
Hoạt động 1: Mô phỏng thuật toán sắp xếp nổi bọt
Đề bài:
Em hãy thực hiện thuật toán sắp xếp nổi bọt để sắp xếp 5 số sau đây theo thứ tự tăng dần. Hãy mô phỏng các bước lặp sắp xếp bằng hình vẽ minh hoạ.
| 3 | 5 | 4 | 1 | 2 |
|---|
Cách giải
Bước 1: Hiểu thuật toán sắp xếp nổi bọt
Thuật toán nổi bọt so sánh hai phần tử đứng cạnh nhau. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. Lặp lại cho đến khi dãy số được sắp xếp.
Bước 2: Thực hiện từng vòng lặp
🔹 Vòng lặp thứ nhất (đưa phần tử nhỏ nhất về vị trí đầu tiên)
| Bước | So sánh | Dãy số | Hành động |
|---|---|---|---|
| Ban đầu | - | 3, 5, 4, 1, 2 | - |
| 1.1 | 3 và 5 | 3, 5, 4, 1, 2 | 3 < 5 → KHÔNG đổi |
| 1.2 | 5 và 4 | 3, 4, 5, 1, 2 | 5 > 4 → Đổi chỗ |
| 1.3 | 5 và 1 | 3, 4, 1, 5, 2 | 5 > 1 → Đổi chỗ |
| 1.4 | 5 và 2 | 3, 4, 1, 2, 5 | 5 > 2 → Đổi chỗ |
→ Kết quả vòng 1: | 3 | 4 | 1 | 2 | 5 |
(Số 5 đã "nổi" lên vị trí cuối cùng)
🔹 Vòng lặp thứ hai (xét từ đầu đến vị trí thứ 4)
| Bước | So sánh | Dãy số | Hành động |
|---|---|---|---|
| Ban đầu | - | 3, 4, 1, 2, 5 | - |
| 2.1 | 3 và 4 | 3, 4, 1, 2, 5 | 3 < 4 → KHÔNG đổi |
| 2.2 | 4 và 1 | 3, 1, 4, 2, 5 | 4 > 1 → Đổi chỗ |
| 2.3 | 4 và 2 | 3, 1, 2, 4, 5 | 4 > 2 → Đổi chỗ |
→ Kết quả vòng 2: | 3 | 1 | 2 | 4 | 5 |
🔹 Vòng lặp thứ ba (xét từ đầu đến vị trí thứ 3)
| Bước | So sánh | Dãy số | Hành động |
|---|---|---|---|
| Ban đầu | - | 3, 1, 2, 4, 5 | - |
| 3.1 | 3 và 1 | 1, 3, 2, 4, 5 | 3 > 1 → Đổi chỗ |
| 3.2 | 3 và 2 | 1, 2, 3, 4, 5 | 3 > 2 → Đổi chỗ |
→ Kết quả vòng 3: | 1 | 2 | 3 | 4 | 5 |
🔹 Vòng lặp thứ tư (xét từ đầu đến vị trí thứ 2)
| Bước | So sánh | Dãy số | Hành động |
|---|---|---|---|
| Ban đầu | - | 1, 2, 3, 4, 5 | - |
| 4.1 | 1 và 2 | 1, 2, 3, 4, 5 | 1 < 2 → KHÔNG đổi |
→ Kết quả vòng 4: | 1 | 2 | 3 | 4 | 5 |
Bước 3: Kết luận
Đáp án: Sau 4 vòng lặp, dãy số được sắp xếp theo thứ tự tăng dần: | 1 | 2 | 3 | 4 | 5 |
💡 Mẹo nhớ: "Nổi bọt - bọt nổi lên" → Phần tử lớn nhất sẽ "nổi" dần về cuối dãy sau mỗi vòng lặp, giống như bọt khí nổi lên mặt nước.
Câu hỏi trắc nghiệm: Thuật toán sắp xếp nổi bọt
Đề bài:
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách:
A. Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách.
B. Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách.
C. Hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.
D. Chèn phần tử vào vị trí thích hợp để đảm bảo danh sách sắp xếp theo đúng thứ tự.
Cách giải
Phân tích từng đáp án:
- Đáp án A: "Chọn phần tử bé nhất đặt vào đầu" → Đây là đặc điểm của thuật toán sắp xếp chọn, không phải nổi bọt. ❌
- Đáp án B: "Chọn phần tử lớn nhất đặt vào đầu" → Không đúng với cả hai thuật toán đã học. ❌
- Đáp án C: "Hoán đổi nhiều lần các phần tử liền kề nếu không đúng thứ tự" → Đây chính xác là cách hoạt động của thuật toán nổi bọt! ✅
- Đáp án D: "Chèn phần tử vào vị trí thích hợp" → Đây là đặc điểm của thuật toán sắp xếp chèn, không phải nổi bọt. ❌
Đáp án: C Thuật toán sắp xếp nổi bọt hoạt động bằng cách hoán đổi nhiều lần các phần tử liền kề nếu giá trị của chúng không đúng thứ tự.
💡 Mẹo nhớ: - Nổi bọt = So sánh và đổi chỗ hai phần tử cạnh nhau - Sắp xếp chọn = Tìm phần tử nhỏ nhất rồi đưa về đầu
🎯 Ghi nhớ: 1. Thuật toán sắp xếp nổi bọt: So sánh và hoán đổi các cặp phần tử liền kề, phần tử lớn sẽ dần "nổi" về cuối dãy. 2. Thuật toán sắp xếp chọn: Tìm phần tử nhỏ nhất trong phần chưa sắp xếp, đưa về vị trí đầu tiên của phần đó. 3. Cả hai thuật toán đều cho kết quả giống nhau (dãy số được sắp xếp), nhưng cách thực hiện khác nhau.