Thuật toán nổi bọt
BÀI 14: THUẬT TOÁN NỔI BỌT
(Bubble Sort - TIN HỌC 7 SÁCH CTST)
1.Sau bài học này học sinh đạt được:
- Nhận biết được quy luật so sánh – hoán đổi trong thuật toán nổi bọt.
- Phân tích được quá trình sắp xếp của thuật toán dựa trên từng bước lặp.
- Giải thích được vì sao thuật toán dừng khi không còn hoán đổi.
- Mô tả được thuật toán nổi bọt dạng sơ đồ khối.
- Vận dụng thuật toán nổi bọt để giải bài toán cụ thể (VD: sắp xếp điểm số, thứ tự tên…).
- Phân tích được đầu vào – đầu ra – điều kiện dừng trong thuật toán.
- So sánh và đánh giá hiệu quả giữa các cách sắp xếp khác nhau.
2. Kiến thức cơ bản
- Thuật toán nổi bọt dùng để sắp xếp một danh sách các phần tử dạng số (mảng) theo thứ tự tăng dần hoặc giảm dần;
- Thuật toán hoạt động bằng cách so sánh từng cặp phần tử liền kề và hoán đổi nếu chúng không theo đúng thứ tự mong muốn.
- Mỗi vòng lặp qua danh sách sẽ đưa phần tử lớn nhất (hoặc nhỏ nhất) nổi lên đúng vị trí — giống như bọt nước nổi lên trên mặt → vì vậy gọi là "nổi bọt".
Ví dụ thuật toán sắp xếp nổi bọt:
2.1 Dữ liệu đầu vào:
- Cho danh sách gồm 5 phần tử số như sau: [5, 3, 4, 1, 2]
2.2 Thuật toán:
Lần lặp 1 (i = 0):
- So sánh 5 và 3 → đổi chỗ → [3, 5, 4, 1, 2]
- So sánh 5 và 4 → đổi chỗ → [3, 4, 5, 1, 2]
- So sánh 5 và 1 → đổi chỗ → [3, 4, 1, 5, 2]
- So sánh 5 và 2 → đổi chỗ → [3, 4, 1, 2, 5] ✅ 5 đã đúng vị trí
Kết quả sau vòng 1: [3, 4, 1, 2, 5]
Lần lặp 2 (i = 1):
- So sánh 3 và 4 → đúng thứ tự → giữ nguyên
- So sánh 4 và 1 → đổi chỗ → [3, 1, 4, 2, 5]
- So sánh 4 và 2 → đổi chỗ → [3, 1, 2, 4, 5]
Kết quả sau vòng 2: [3, 1, 2, 4, 5]
Lần lặp 3 (i = 2):
- So sánh 3 và 1 → đổi chỗ → [1, 3, 2, 4, 5]
- So sánh 3 và 2 → đổi chỗ → [1, 2, 3, 4, 5]
Kết quả sau vòng 3: [1, 2, 3, 4, 5]
Lần lặp 4 (i = 3):
- So sánh 1 và 2 → đúng thứ tự → giữ nguyên
- Không còn hoán đổi → kết thúc sớm (có thể tối ưu tại đây)
2.3 Kết quả sau khi sắp xếp mảng tăng dần:
[1, 2, 3, 4, 5]3. Mô phỏng mô hình:
Học sinh lựa chọn mảng nhập thủ công hoặc mảng ngẫu nhiên.
3.1 Trường hợp lựa chọn mảng thủ công:
- Bước 1: Nhập các phần tử cách nhau bởi dấu phẩy: [5,7,2,6,1]
- Bước 2: Chọn nút tạo mảng
- Bước 3: Chọn tốc độ sắp xếp
- Bước 4: Chọn nút bắt đầu sắp xếp để xem kết quả.
3.2 Trường hợp chọn mảng ngẫu nhiên
- Bước 1: Nhập số phần tử
- Bước 2: Chọn nút tạo mảng
- Bước 3: Chọn tốc độ sắp xếp
- Bước 4: Chọn nút bắt đầu sắp xếp để xem kết quả.
🔁 MÔ PHỎNG BUBBLE SORT + HIỆU ỨNG
🧮 So sánh: 0
🔄 Hoán đổi: 0
🔁 Vòng lặp: 0
📋 Các bước sắp xếp:
Bạn đánh giá bài viết này thế nào?
★
★
★
★
★
Post a Comment