Sắp xếp cơ bản (Bubble · Selection · Insertion)

Bạn sẽ học được gì

Ba thuật toán sắp xếp đầu đời: nổi bọt (bubble), chọn (selection) và chèn (insertion). Cả ba đều chậm — O(n^2) — nhưng chúng là cánh cửa để bạn cảm được sắp xếp thực sự diễn ra thế nào. Đặc biệt, bạn sẽ hiểu vì sao insertion sort lại nhanh bất ngờ khi mảng đã gần được sắp xếp.

1. Trực quan: ba cách sắp một cỗ bài

Hình dung bạn cầm một xấp bài lộn xộn trên tay. Có ba kiểu người sắp bài:

• Người nổi bọt (bubble): so từng cặp kề nhau, thấy cặp nào sai chỗ thì đổi. Lặp đi lặp lại, quân lớn nhất "nổi" dần về cuối như bọt khí nổi lên mặt nước.
• Người chọn (selection): mỗi vòng, mắt quét cả xấp tìm quân nhỏ nhất còn lại, rồi đặt nó vào đúng vị trí đầu. Như khi bạn xếp huy chương: tìm hạng nhất trước, rồi hạng nhì...
• Người chèn (insertion): cầm từng quân mới, luồn nó vào đúng chỗ trong phần đã sắp bên trái. Đây chính là cách phần lớn chúng ta sắp bài trên tay thật ngoài đời.

Bubble : so cap ke nhau, day phan tu lon ve cuoi
   [5 3 8 1]  ->  [3 5 1 8]  ->  ... 8 noi ve cuoi

Selection: chon nho nhat dat vao dau
   [5 3 8 1]  ->  chon 1  ->  [1 | 3 8 5]  ->  chon 3 ...

Insertion: luon phan tu moi vao phan da sap
   da sap [3 5] | lay 8 -> [3 5 8] | lay 1 -> luon ve dau [1 3 5 8]

2. Ý tưởng cốt lõi của từng cái

Thuật toán	Mỗi vòng làm gì	Tốt nhất	Trung bình	Xấu nhất
Bubble	đẩy phần tử lớn nhất về cuối bằng đổi chỗ liên tiếp	O(n)*	O(n^2)	O(n^2)
Selection	tìm nhỏ nhất còn lại, đưa lên đầu	O(n^2)	O(n^2)	O(n^2)
Insertion	luồn phần tử mới vào phần đã sắp bên trái	O(n)	O(n^2)	O(n^2)

* Bubble đạt O(n) nếu có cờ "đã không đổi chỗ nào nữa thì dừng" và mảng đã sắp sẵn.

Điểm mấu chốt: Selection luôn O(n^2) dù mảng đã sắp (vẫn quét tìm nhỏ nhất mỗi vòng). Còn Insertion thì biết tận dụng trật tự sẵn có — nếu phần tử mới đã lớn hơn phần tử cuối của vùng đã sắp, nó dừng ngay, không dịch gì.

3. Chạy debug: insertion sort luồn một phần tử

Bước qua để thấy phần tử 2 được luồn về đúng chỗ trong vùng đã sắp [1, 4, 5].

🐞 Insertion: chèn 2 vào [1, 4, 5]Bước 1/5

1a = [1, 4, 5, 2]
2key = a[3]        # key = 2
3j = 2             # xet tu cuoi vung da sap
4# 5 > 2 -> day 5 sang phai
5# 4 > 2 -> day 4 sang phai
6# 1 < 2 -> dung, chen 2 vao day

Biến tại bước này

a	[1, 4, 5, 2]

👉 Vùng đã sắp là [1, 4, 5]; cần chèn 2.

4. Code chạy được: cả ba thuật toán

Đang tải trình chạy code…

5. Phân tích: chậm, nhưng dạy ta nhiều

• Vì sao cả ba đều O(n^2)? Đều có vòng lặp trong vòng lặp: với mỗi phần tử, ta lại quét một phần mảng. n phần tử nhân n lần quét → n^2 thao tác.
• Bộ nhớ: cả ba sắp tại chỗ (in-place), chỉ tốn O(1) bộ nhớ phụ.
• Bẫy thường gặp: dùng các thuật toán này cho mảng lớn (hàng triệu phần tử). Với n = 1_000_000, n^2 là một nghìn tỷ phép — máy sẽ "đứng hình". Khi đó hãy chuyển sang merge/quick sort.
• Điểm sáng của insertion: nếu mảng gần như đã sắp (mỗi phần tử lệch khỏi chỗ đúng vài bước), insertion gần như chạy O(n). Đó là lý do nó được dùng làm bước cuối trong nhiều thư viện sắp xếp thực tế.

6. Mẫu nhận diện

• Mảng nhỏ (vài chục phần tử) hoặc gần như đã sắp → insertion sort là lựa chọn gọn, nhanh.
• Cần thuật toán dễ cài, dễ giải thích trong phỏng vấn nhập môn → một trong ba cái này.
• Mảng lớn, lộn xộn → ĐỪNG dùng O(n^2); hãy nhớ tới merge sort hoặc quick sort ở bài sau.

7. 🎮 Trò chơi: Hiểu sắp xếp cơ bản

🎮 Bubble · Selection · InsertionCâu 1/4· Điểm 0· 🔥 0

Cả ba đều O(n^2), nhưng hành xử khác nhau trên dữ liệu khác nhau.

Sau MỘT vòng bubble đầu tiên trên [3, 1, 2], phần tử nào chắc chắn về đúng chỗ cuối?

a = [3, 1, 2]
# bubble: so cap (3,1) doi -> [1,3,2]; (3,2) doi -> [1,2,3]
print([1, 2, 3])

8. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Độ phức tạp trung bình của cả ba thuật toán cơ bản là?

2. Khi nào insertion sort là lựa chọn tốt nhất trong ba cái?

3. Điểm chung về bộ nhớ của ba thuật toán này là?

9. Hoàn thành

…

☑️ Tiếp theo: 3.1.2 — Merge sort (chia để trị, đạt O(n log n)).