Giải Vận dụng 2 trang 82 SGK Tin học 9
Đề bài
Vẽ sơ đồ khối của giải thuật sắp xếp nổi bọt để sắp xếp một dãy số theo thứ tự tăng dần.
Lời giải
## Sắp xếp nổi bọt (tăng dần) — sơ đồ khối
Ý tưởng: Lặp lại nhiều lượt, mỗi lượt đi từ đầu dãy, so sánh hai phần tử kề nhau. Nếu phần tử đứng trước lớn hơn phần tử đứng sau () thì đổi chỗ để số lớn "nổi" dần về cuối. Sau mỗi lượt, phần tử lớn nhất trong phần còn lại được đẩy về đúng vị trí.
Các khối dùng trong sơ đồ (quy ước SGK):
- Hình ô van: *Bắt đầu / Kết thúc*
- Hình bình hành: *Nhập / Xuất dữ liệu*
- Hình chữ nhật: *bước xử lí (tính toán, gán)*
- Hình thoi: *điều kiện (Đúng / Sai)*
Sơ đồ khối:
```
┌───────────────┐
│ Bắt đầu │ (ô van)
└──────┬────────┘
│
┌───────────┴──────────────┐
│ Nhập n và dãy a_1 … a_n │ (hình bình hành)
└───────────┬──────────────┘
│
┌────┴────┐
│ i ← 1 │ (hình chữ nhật)
└────┬────┘
│ ◄─────────────────────────────┐
╱──────┴───────╲ │
╱ i ≤ n − 1 ? ╲── Sai ──┐ │
╲ (hình thoi) ╱ │ │
╲──────┬───────╱ │ │
Đúng│ │ │
┌────┴────┐ │ │
│ j ← 1 │ │ │
└────┬────┘ │ │
│ ◄──────────────────────────┐ │
╱──────┴───────╲ │ │ │
╱ j ≤ n − i ? ╲─ Sai ─► i ← i + 1 ──┼──┘
╲ ╱ │ │
╲──────┬───────╱ │ │
Đúng│ │ │
╱──────┴───────╲ │ │
╱ a_j > a_{j+1}? ╲─ Sai ─┐ │ │
╲ ╱ │ │ │
╲──────┬───────╱ │ │ │
Đúng│ │ │ │
┌───────────┴───────────┐ │ │ │
│ Đổi chỗ a_j ↔ a_{j+1} │ │ │ │
└───────────┬───────────┘ │ │ │
│ ◄──────────────┘ │ │
┌────┴────┐ │ │
│ j ← j+1 │─────────────┼───────────┘
└─────────┘ │
│ (nhánh i > n−1)
┌──────────────┴───────────┐
│ Xuất dãy a_1 … a_n │ (hình bình hành)
└──────────────┬───────────┘
┌──────┴───────┐
│ Kết thúc │ (ô van)
└──────────────┘
```
Giải thích các bước:
1. Nhập số lượng phần tử và dãy .
2. Biến đếm số lượt so sánh, chạy từ đến .
3. Biến chỉ vị trí cặp kề nhau trong mỗi lượt, chạy từ đến (vì sau lượt đã có phần tử lớn nhất nằm đúng cuối dãy).
4. Nếu thì đổi chỗ hai phần tử; ngược lại giữ nguyên, rồi tăng .
5. Khi , dãy đã được sắp xếp tăng dần thì xuất kết quả và kết thúc.
Kết luận: Thuật toán dừng sau lượt, cho dãy .
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.