Sách giáo khoa Tin học 9

Giải Vận dụng 2 trang 82 SGK Tin học 9

Bài 15. Bài toán tin học   Đã kiểm

Đề 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 (aj>aj+1a_j > a_{j+1}) 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ử nn và dãy a1,a2,…,ana_1, a_2, \ldots, a_n.
2. Biến ii đếm số lượt so sánh, chạy từ 11 đến n−1n-1.
3. Biến jj chỉ vị trí cặp kề nhau trong mỗi lượt, chạy từ 11 đến n−in-i (vì sau ii lượt đã có ii phần tử lớn nhất nằm đúng cuối dãy).
4. Nếu aj>aj+1a_j > a_{j+1} thì đổi chỗ hai phần tử; ngược lại giữ nguyên, rồi tăng jj.
5. Khi i>n−1i > n-1, 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 n−1n-1 lượt, cho dãy a1≤a2≤⋯≤ana_1 \le a_2 \le \cdots \le a_n.

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.