🫧
Thuật Toán
Chapter 6 · Lưu Đồ & Thuật Toán
Thuật Toán
Sắp Xếp
Bubble Sort, Selection Sort, Insertion Sort — 3 thuật toán sắp xếp cơ bản và cách biểu diễn bằng lưu đồ!
Phần 1 — Bubble Sort (Sắp xếp nổi bọt)
🫧 Bubble Sort
So sánh cặp liền kề, đẩy phần tử lớn lên cuối
Ý tưởng: Duyệt mảng nhiều lần. Mỗi lần so sánh 2 phần tử liền kề — nếu sai thứ tự thì đổi chỗ. Phần tử lớn nhất "nổi" dần về cuối như bọt khí.
Mảng ban đầu: [5, 3, 8, 1, 4]
Sau vòng 1: Phần tử lớn nhất (8) về cuối ↓
Kết quả cuối: [1, 3, 4, 5, 8] ✅
FOR i = 0 TO n-2 DO
FOR j = 0 TO n-2-i DO
IF A[j] > A[j+1] THEN
tam = A[j] ← hoán đổi
A[j] = A[j+1]
A[j+1] = tam
| Vòng i | Vòng j | So sánh | Hoán đổi? | Mảng sau bước |
|---|---|---|---|---|
| 0 | 0 | A[0]=5 > A[1]=3 | ✓ Đổi | [3,5,8,1,4] |
| 0 | 1 | A[1]=5 > A[2]=8? | ✗ Không | [3,5,8,1,4] |
| 0 | 2 | A[2]=8 > A[3]=1 | ✓ Đổi | [3,5,1,8,4] |
| 0 | 3 | A[3]=8 > A[4]=4 | ✓ Đổi | [3,5,1,4,8] |
| ... tiếp tục các vòng i=1,2,3 ... | [1,3,4,5,8] ✅ | |||
Hoán đổi 3 bước — cần biến tạm! Không thể viết A[j]=A[j+1]; A[j+1]=A[j] vì sẽ mất dữ liệu. Phải dùng biến
tam làm trung gian!Phần 2 — Selection Sort (Chọn trực tiếp)
🎯 Selection Sort
Mỗi vòng chọn phần tử nhỏ nhất → đặt vào đầu
Ý tưởng: Mỗi vòng lặp i, tìm phần tử nhỏ nhất trong A[i..n-1], rồi hoán đổi nó với A[i]. Sau i vòng, i phần tử đầu đã được sắp xếp đúng.
[5, 3, 8, 1, 4] → Vòng 1: Tìm min từ vị trí 0
Đổi A[0]↔A[3]: [1, 3, 8, 5, 4] — 1 đã đúng vị trí ✓
FOR i = 0 TO n-2 DO
min_idx = i ← giả sử phần tử i là nhỏ nhất
FOR j = i+1 TO n-1 DO
IF A[j] < A[min_idx] THEN
min_idx = j ← cập nhật vị trí min
IF min_idx ≠ i THEN
Hoán đổi A[i] ↔ A[min_idx]
| Vòng i | Tìm min trong | min_idx | Hoán đổi | Mảng |
|---|---|---|---|---|
| 0 | A[0..4] | 3 (giá trị 1) | A[0]↔A[3] | [1,3,8,5,4] |
| 1 | A[1..4] | 1 (giá trị 3) | Không đổi | [1,3,8,5,4] |
| 2 | A[2..4] | 4 (giá trị 4) | A[2]↔A[4] | [1,3,4,5,8] |
| 3 | A[3..4] | 3 (giá trị 5) | Không đổi | [1,3,4,5,8] ✅ |
Phần 3 — Insertion Sort (Chèn trực tiếp)
📌 Insertion Sort
Lấy từng phần tử chèn vào đúng vị trí trong phần đã sắp xếp
Giống như sắp xếp bài trong tay khi chơi bài — mỗi lần nhận bài mới, chèn vào đúng chỗ trong những lá đã sắp.
[5, 3, 8, 1, 4] — Xem từng phần tử và chèn vào đúng chỗ
3 < 5 → chèn 3 vào trước 5: [3, 5, 8, 1, 4]
FOR i = 1 TO n-1 DO
key = A[i] ← phần tử cần chèn
j = i - 1
WHILE j ≥ 0 AND A[j] > key DO
A[j+1] = A[j] ← dịch phải
j = j - 1
A[j+1] = key ← đặt vào đúng chỗ
| i | key | Dịch phần tử | Mảng sau chèn |
|---|---|---|---|
| 1 | 3 | 5 → dịch phải | [3,5,8,1,4] |
| 2 | 8 | Không dịch | [3,5,8,1,4] |
| 3 | 1 | 8,5,3 → dịch phải | [1,3,5,8,4] |
| 4 | 4 | 8,5 → dịch phải | [1,3,4,5,8] ✅ |
Phần 4 — So sánh 3 thuật toán
Độ phức tạp & Khi nào dùng cái nào?
| Thuật toán | Tốt nhất | Trung bình | Tệ nhất | Nên dùng khi |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Học thuật, mảng nhỏ ≤ 20 |
| Selection Sort | O(n²) | O(n²) | O(n²) | Ít thao tác hoán đổi nhất |
| Insertion Sort | O(n) | O(n²) | O(n²) | Mảng gần đã sắp xếp |
📚 Ghi nhớ cho kỳ thi: Cả 3 thuật toán đều có độ phức tạp O(n²) ở trường hợp tệ nhất. Trong thực tế có các thuật toán nhanh hơn như Merge Sort O(n log n), Quick Sort O(n log n) — sẽ học ở lớp cao hơn.
🧩 Kiểm tra nhanh!
Chapter 6 — Thuật toán sắp xếp
Bubble Sort so sánh các phần tử thế nào?
→ So sánh từng cặp liền kề, đổi nếu sai thứ tự
→ So sánh từng cặp liền kề, đổi nếu sai thứ tự
Selection Sort chọn và đặt phần tử nào?
→ Chọn phần tử nhỏ nhất đặt vào đầu dãy chưa sắp
→ Chọn phần tử nhỏ nhất đặt vào đầu dãy chưa sắp
Hoán đổi 2 phần tử cần mấy bước? Tại sao?
→ 3 bước — cần biến tam để không mất dữ liệu
→ 3 bước — cần biến tam để không mất dữ liệu
Sắp xếp [4,2,7,1] bằng Selection Sort vòng 1: kết quả?
→ [1,2,7,4] — đổi 4 và 1
→ [1,2,7,4] — đổi 4 và 1