Giải Tin Học 7 trang 80
Lời giải chi tiết SGK Lớp 7 · Môn Tin Há»c · Trang 80–81
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ạ.
Dãy số ban đầu: 3, 5, 4, 1, 2
Cách giải
Nguyên tắc của sắp xếp 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 được sắp xếp.
Dãy ban đầu: | 3 | 5 | 4 | 1 | 2 |
🔄 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 | Kết quả | Dãy hiện tại |
|---|---|---|---|
| 1.1 | So sánh 3 và 5 | 3 < 5 → KHÔNG đổi | 3, 5, 4, 1, 2 |
| 1.2 | So sánh 5 và 4 | 5 > 4 → Đổi chỗ | 3, 4, 5, 1, 2 |
| 1.3 | So sánh 5 và 1 | 5 > 1 → Đổi chỗ | 3, 4, 1, 5, 2 |
| 1.4 | So sánh 5 và 2 | 5 > 2 → Đổi chỗ | 3, 4, 1, 2, 5 |
Kết quả vòng lặp 1: | 3 | 4 | 1 | 2 | 5 |
→ Số 5 (lớn nhất) đã "nổi" lên vị trí cuối cùng.
🔄 VÒNG LẶP THỨ HAI (Xét từ vị trí 1 đến vị trí 4)
| Bước | So sánh | Kết quả | Dãy hiện tại |
|---|---|---|---|
| 2.1 | So sánh 3 và 4 | 3 < 4 → KHÔNG đổi | 3, 4, 1, 2, 5 |
| 2.2 | So sánh 4 và 1 | 4 > 1 → Đổi chỗ | 3, 1, 4, 2, 5 |
| 2.3 | So sánh 4 và 2 | 4 > 2 → Đổi chỗ | 3, 1, 2, 4, 5 |
Kết quả vòng lặp 2: | 3 | 1 | 2 | 4 | 5 |
→ Số 4 đã "nổi" lên vị trí thứ 4.
🔄 VÒNG LẶP THỨ BA (Xét từ vị trí 1 đến vị trí 3)
| Bước | So sánh | Kết quả | Dãy hiện tại |
|---|---|---|---|
| 3.1 | So sánh 3 và 1 | 3 > 1 → Đổi chỗ | 1, 3, 2, 4, 5 |
| 3.2 | So sánh 3 và 2 | 3 > 2 → Đổi chỗ | 1, 2, 3, 4, 5 |
Kết quả vòng lặp 3: | 1 | 2 | 3 | 4 | 5 |
→ Số 3 đã "nổi" lên vị trí thứ 3.
🔄 VÒNG LẶP THỨ TƯ (Xét từ vị trí 1 đến vị trí 2)
| Bước | So sánh | Kết quả | Dãy hiện tại |
|---|---|---|---|
| 4.1 | So sánh 1 và 2 | 1 < 2 → KHÔNG đổi | 1, 2, 3, 4, 5 |
Kết quả vòng lặp 4: | 1 | 2 | 3 | 4 | 5 |
Đáp án: Dãy sau khi sắp xếp tăng dần: 1, 2, 3, 4, 5
Câu hỏi trắc nghiệm
Đề 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 sắp xếp nổi bọt. ❌
- Đáp án B: "Chọn phần tử lớn nhất đặt vào đầu" → Cũng là một dạng của sắp xếp chọn. ❌
- Đá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ự" → Đúng! Đây chính xác là cách hoạt động của sắp xếp 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. ❌
Đáp án: C
💡 Mẹo nhớ: - Nổi bọt = So sánh và đổi chỗ hai phần tử liền kề (như bọt khí nổi lên từ từ) - Sắp xếp chọn = Tìm phần tử nhỏ nhất rồi đưa về đầu
🎯 Ghi nhớ: - 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ề nhiều lần cho đến khi dãy được sắp xếp. - 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 đó, rồi lặp lại với các vị trí tiếp theo. - Cả hai thuật toán đều cho kết quả giống nhau, nhưng cách thực hiện khác nhau.