Bộ ba sắp xếp O(n²): bubble, selection, insertion

Giới thiệu

Bài này học 3 cách sắp xếp đơn giản nhất. Bạn biết khi nào chúng vẫn đủ dùng.

Kiến thức cần nhớ

Bubble sort — bong bóng nổi lên

• So sánh từng cặp kề, sai thì đổi chỗ.
• Sau 1 lượt, số lớn nhất ra cuối.
• Thêm cờ hiệu: không đổi chỗ nào thì dừng.
• Ví dụ đời thường: bọt to nổi lên mặt nước.
• Đã sắp xếp thì chỉ tốn $O(n)$.

Selection sort — mỗi lượt 1 lần đổi

• Mỗi lượt tìm số lớn nhất rồi đổi 1 lần.
• Tổng cả bài chỉ đổi tối đa n-1 lần.
• Ví dụ đời thường: chọn quả to nhất bỏ vào rổ.
• Hợp khi chi phí ghi đắt hơn đọc.

Insertion sort — chèn lá bài

• Lấy từng lá chèn vào đoạn đã xếp.
• Dữ liệu gần xếp rồi thì chạy rất nhanh.
• Dữ liệu ngược thì chậm $O(n^2)$.
• Ví dụ đời thường: xếp bài trên tay.

Ví dụ

• Input: 5, 4, 3, 2, 1 chạy selection. Output: 4 lượt, nhưng chỉ 2 lần đổi thật (2 lượt sau phần tử đã đúng chỗ), dãy tăng dần.
• Giải thích: mỗi lượt chỉ đổi đúng 1 lần.

# 1 lượt bubble đẩy số lớn ra cuối
for i in range(len(a) - 1):
    if a[i] > a[i+1]:  # cặp kề sai thứ tự
        a[i], a[i+1] = a[i+1], a[i]  # đổi chỗ

💻 Bài tập

Ngôn ngữ: C++ (hoặc C). Nộp vào day-010/. Mọi hàm sắp xếp tại chỗ, tăng dần.

Bài 1: Ba thuật toán có bộ đếm

struct Stats { long long comparisons = 0; long long swaps = 0; long long passes = 0; };
void bubbleSort(std::vector<int> &a, Stats &st);     // có cờ dừng sớm
void selectionSort(std::vector<int> &a, Stats &st);
void insertionSort(std::vector<int> &a, Stats &st);  // "swaps" = số lần dịch phần tử

Ràng buộc: không dùng std::sort. Mỗi hàm tăng đúng bộ đếm tại chỗ so sánh và đổi chỗ.

bubble    [5,1,4,2,8]  -> [1,2,4,5,8]; swaps=4
selection [5,4,3,2,1]  -> [1,2,3,4,5]; swaps=2  (bỏ qua đổi chỗ với chính nó)
insertion [1,2,3,4,5]  -> comparisons=4, swaps=0
bubble    [1,2,3,4,5]  -> passes=1 (cờ dừng sớm)
mảng rỗng, 1 phần tử   -> không lỗi, stats = 0

Bài 2: Bảng đếm trên 4 loại dữ liệu

Sinh 4 mảng cỡ $n = 1000$: ngẫu nhiên, đã xếp, xếp ngược, gần xếp (xếp rồi đổi 10 cặp ngẫu nhiên). Chạy 3 thuật toán và in:

data         algo        comparisons   swaps
random       bubble      ...           ...
random       selection   ...           ...
...

Viết 4 câu kết luận: thuật toán nào thắng ở dữ liệu nào, vì sao.

Bài 3: Tính ổn định và sắp theo khóa (nâng cao)

1. Đổi 3 hàm thành template nhận comparator: template<class T, class Cmp> void insertionSort(std::vector<T>&, Cmp).
2. Sắp danh sách sinh viên {name, score} theo score tăng dần.
3. Viết test phát hiện thuật toán không ổn định: hai sinh viên cùng điểm phải giữ thứ tự ban đầu.

[(An,8), (Bình,7), (Chi,8), (Dũng,7)] sắp theo score
insertion / bubble -> [(Bình,7), (Dũng,7), (An,8), (Chi,8)]   ổn định
selection          -> có thể đảo An và Chi: tìm input cụ thể chứng minh

✅ Tiêu chí hoàn thành

• Test mẫu pass, có test so với std::sort trên 1000 mảng ngẫu nhiên.
• Bảng Bài 2 có số thật và 4 câu kết luận.
• Bài 3 có input cụ thể chứng minh selection sort không ổn định.
• Giải thích được vì sao insertion sort chạy $O(n)$ trên dữ liệu gần xếp.

❓ Câu hỏi ôn tập

• Bubble sort hoạt động thế nào?
• Cờ hiệu giúp gì cho best case?
• Selection đổi chỗ mấy lần mỗi lượt?
• Khi nào insertion chạy nhanh nhất?

🌕 Bạn đã hoàn thành ngày 10. Làm hết bài tập phía trên rồi sang ngày tiếp theo.