Giao diện
Selection Sort — Sắp xếp chọn
Năm 2019, một kỹ sư firmware tại một công ty IoT Việt Nam cần sắp xếp 64 giá trị cảm biến trên chip EEPROM — loại bộ nhớ chỉ chịu được khoảng 100.000 lần ghi trước khi hỏng. Bubble Sort với hàng trăm swap mỗi lần chạy sẽ "giết" chip trong vài tháng. Selection Sort, với tối đa n − 1 lần ghi, giữ chip sống hàng năm trời.
Selection Sort không phải "bài tập cho người mới". Đây là thuật toán tối ưu số lần ghi bộ nhớ — đặc tính cực kỳ quý giá khi chi phí mỗi lần write cao hơn chi phí read hàng nghìn lần. Trong khi Insertion Sort và Bubble Sort có thể thực hiện O(n²) swap ở worst case, Selection Sort bảo đảm chỉ O(n) swap bất kể input.
Bài này sẽ cho bạn hiểu rõ cơ chế hoạt động, tại sao thuật toán không ổn định theo mặc định, và chính xác khi nào nó là lựa chọn tốt hơn Insertion Sort.
Bức tranh tư duy
Hình dung bạn là giáo viên thể dục đang xếp học sinh theo chiều cao tăng dần.
Bạn không yêu cầu các em đổi chỗ liên tục với nhau (Bubble Sort). Thay vào đó, bạn đứng ở đầu hàng, nhìn một lượt toàn bộ hàng còn lại, chọn ra em thấp nhất, rồi gọi em đó lên đứng vị trí đầu tiên — một lần đổi chỗ duy nhất. Xong, bạn bước sang vị trí thứ hai, lại nhìn hết phần còn lại, chọn em thấp nhất tiếp theo, đổi chỗ. Cứ thế cho đến hết.
Vòng 1: [64, 25, 12, 22, 11] → tìm min = 11 → swap(64, 11)
[11 | 25, 12, 22, 64] ✓ đã chọn
Vòng 2: [11, 25, 12, 22, 64] → tìm min = 12 → swap(25, 12)
[11, 12 | 25, 22, 64] ✓ đã chọn
Vòng 3: [11, 12, 25, 22, 64] → tìm min = 22 → swap(25, 22)
[11, 12, 22 | 25, 64] ✓ đã chọn
Vòng 4: [11, 12, 22, 25, 64] → tìm min = 25 → không đổi
[11, 12, 22, 25 | 64] ✓ đã chọnBản chất: Mỗi vòng lặp tốn nhiều công nhìn (comparison) nhưng chỉ một lần đổi chỗ (swap). Đó chính là đặc trưng cốt lõi của Selection Sort — đánh đổi thời gian so sánh để tiết kiệm thao tác ghi.
💡 Khi nào analogy này bị breakdown
Trong đời thực, giáo viên có thể nhìn cả hàng và nhận ra ngay ai thấp nhất (O(1) bằng thị giác). Nhưng máy tính phải quét tuần tự từng phần tử — không có "thị giác" để nhảy cóc. Vì vậy số comparison luôn là Θ(n²), không có best case nào nhanh hơn.
Cốt lõi kỹ thuật
Cơ chế hoạt động
Selection Sort chia mảng thành hai vùng bằng một ranh giới ảo tại vị trí i:
- Vùng trái
[0..i-1]: đã sắp xếp, chứaiphần tử nhỏ nhất. - Vùng phải
[i..n-1]: chưa sắp xếp.
Mỗi vòng lặp thứ i:
- Quét toàn bộ vùng phải để tìm chỉ số
minIdxcủa phần tử nhỏ nhất. - Swap
arr[i]vớiarr[minIdx]. - Mở rộng vùng trái thêm một phần tử.
Sau đúng n − 1 vòng, mảng hoàn toàn có thứ tự.
Tại sao luôn có n(n−1)/2 phép so sánh?
Ở vòng i, thuật toán quét n − i − 1 phần tử. Tổng số comparison:
(n-1) + (n-2) + ... + 1 = n(n-1)/2Khác với Insertion Sort (best case O(n) khi mảng đã sắp xếp) hay Bubble Sort (có thể dừng sớm với cờ swapped), Selection Sort không có cơ chế dừng sớm. Dù input đã sắp xếp hay ngẫu nhiên, số comparison luôn chính xác n(n−1)/2. Đây là Θ(n²) — không phải O(n²) theo nghĩa "tối đa", mà là luôn luôn.
Tính ổn định (Stability)
Selection Sort không ổn định (unstable) theo mặc định. Ví dụ:
Input: [4a, 3, 4b, 1]
Vòng 1: swap(4a, 1) → [1, 3, 4b, 4a] ← 4a nhảy ra sau 4bSau khi sắp xếp: [1, 3, 4b, 4a] — thứ tự tương đối giữa 4a và 4b bị đảo.
Cách biến Selection Sort thành stable: Thay vì swap, ta chèn (insert) phần tử nhỏ nhất vào vị trí i bằng cách dịch các phần tử trung gian sang phải. Tuy nhiên, điều này tăng số lần ghi từ O(n) lên O(n²) — mất đi ưu điểm cốt lõi. Trong thực tế, nếu cần stable sort, hãy dùng Insertion Sort hoặc Merge Sort.
Triển khai chuẩn
cpp
#include <algorithm>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
std::swap(arr[i], arr[minIdx]);
}
}
}python
def selection_sort(arr: list[int]) -> None:
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]java
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
}go
func selectionSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
minIdx := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIdx] {
minIdx = j
}
}
if minIdx != i {
arr[i], arr[minIdx] = arr[minIdx], arr[i]
}
}
}🔍 Chi tiết triển khai
Điều kiện if (minIdx != i) không bắt buộc về mặt logic — swap một phần tử với chính nó vẫn đúng. Nhưng nó tránh một lần ghi không cần thiết, đặc biệt quan trọng trên bộ nhớ có chi phí write cao. Trên hardware thông thường, branch prediction miss có thể khiến check này chậm hơn — hãy đo benchmark trước khi quyết định.
Thực chiến
Tình huống: Sắp xếp dữ liệu trên EEPROM vi điều khiển
Bối cảnh: Hệ thống IoT thu thập nhiệt độ từ 32 cảm biến, lưu vào EEPROM (AT24C256 — giới hạn ~1 triệu chu kỳ ghi). Mỗi phút cần sắp xếp giá trị để tính median lọc nhiễu.
Mục tiêu: Sắp xếp 32 phần tử với số lần write tối thiểu để kéo dài tuổi thọ chip.
Phân tích lựa chọn:
| Thuật toán | Swap worst case | Phù hợp? |
|---|---|---|
| Bubble Sort | O(n²) = 496 | ❌ Quá nhiều write |
| Insertion Sort | O(n²) = 496 | ❌ Shift = nhiều write |
| Selection Sort | O(n) = 31 | ✅ Tối ưu write |
std::sort (Introsort) | O(n log n) | ⚠️ Nhanh hơn nhưng nhiều write hơn |
Với n = 32, Selection Sort thực hiện tối đa 31 swap (62 lần ghi). Bubble Sort có thể lên tới 496 swap (992 lần ghi). Chênh lệch 16 lần — đủ để kéo dài tuổi thọ EEPROM từ 2 năm lên hơn 30 năm khi chạy liên tục mỗi phút.
Kết luận thực chiến: Selection Sort là lựa chọn đúng khi (1) kích thước dữ liệu nhỏ (n < 100), (2) chi phí write đắt hơn read, và (3) không cần stable sort. Ngoài các điều kiện này, hãy dùng Insertion Sort hoặc các thuật toán O(n log n).
Sai lầm điển hình
❌ Sai lầm 1: Giả định Selection Sort ổn định
Vấn đề: Nhiều lập trình viên nhầm lẫn Selection Sort là stable vì "nó chỉ chọn phần tử nhỏ nhất".
python
# Input có hai phần tử giá trị bằng nhau
data = [(4, 'a'), (3, 'x'), (4, 'b'), (1, 'y')]
# Sau selection sort theo giá trị số:
# Kết quả: [(1,'y'), (3,'x'), (4,'b'), (4,'a')] ← 'a' và 'b' bị đảo!Tại sao sai: Thao tác swap đưa phần tử tại vị trí i nhảy xa đến vị trí minIdx, vượt qua các phần tử cùng giá trị. Trong production, nếu bạn dùng Selection Sort để sắp xếp bảng dữ liệu theo cột — thứ tự gốc của các dòng cùng giá trị sẽ bị xáo trộn, gây lỗi UI khó debug.
Giải pháp: Nếu cần stable sort, dùng Insertion Sort hoặc Merge Sort. Không cố "fix" Selection Sort bằng cách chèn thay vì swap — bạn sẽ mất lợi thế O(n) swap.
❌ Sai lầm 2: Nghĩ rằng mảng đã sắp xếp sẽ chạy nhanh hơn
Vấn đề: Với Bubble Sort và Insertion Sort, input đã sắp xếp cho best case O(n). Nhiều người áp dụng logic tương tự cho Selection Sort.
Input đã sort: [1, 2, 3, 4, 5]
Selection Sort vẫn thực hiện:
Vòng 1: quét 4 phần tử → tìm min = 1 → không swap
Vòng 2: quét 3 phần tử → tìm min = 2 → không swap
Vòng 3: quét 2 phần tử → tìm min = 3 → không swap
Vòng 4: quét 1 phần tử → tìm min = 4 → không swap
Tổng: 4 + 3 + 2 + 1 = 10 comparisons = n(n-1)/2Tại sao sai: Selection Sort không có cơ chế nhận biết mảng đã sắp xếp. Nó luôn quét toàn bộ phần còn lại để tìm minimum — bất kể input. Best case = Worst case = Θ(n²) comparisons.
❌ Sai lầm 3: Nhầm lẫn với Bubble Sort
Vấn đề: Cả hai đều O(n²) và hay được dạy cùng nhau, dẫn đến nhầm lẫn cơ chế.
| Đặc điểm | Selection Sort | Bubble Sort |
|---|---|---|
| Cơ chế | Tìm min, swap về đầu | So sánh cặp liền kề, đẩy max về cuối |
| Swap/vòng | Tối đa 1 | Có thể nhiều |
| Best case time | Θ(n²) | O(n) với cờ swapped |
| Stable? | ❌ Không | ✅ Có |
Ghi nhớ: Selection Sort chọn rồi mới đổi (1 swap/vòng). Bubble Sort đổi liên tục trong khi quét (nhiều swap/vòng).
Under the Hood
Hiệu năng
| Metric | Best | Average | Worst | Ghi chú |
|---|---|---|---|---|
| Comparisons | Θ(n²) | Θ(n²) | Θ(n²) | Luôn n(n−1)/2, không phụ thuộc input |
| Swaps | 0 | O(n) | O(n) | Tối đa n−1 swap |
| Space | O(1) | O(1) | O(1) | In-place, chỉ cần biến tạm |
Phân tích memory write
Đây là lợi thế then chốt. So sánh tổng số write operations cho n = 1000:
| Thuật toán | Writes (worst case) |
|---|---|
| Selection Sort | ~2.000 (n−1 swap × 2 write/swap) |
| Bubble Sort | ~1.000.000 (n²/2 swap × 2 write/swap) |
| Insertion Sort | ~500.000 (n²/2 shift, mỗi shift = 1 write) |
Selection Sort ghi ít hơn 500 lần so với Bubble Sort. Trên bộ nhớ flash, SSD, hay bất kỳ phương tiện có write endurance giới hạn, sự khác biệt này quyết định tuổi thọ phần cứng.
Cache behavior
Selection Sort có locality kém hơn Insertion Sort. Vòng lặp trong quét toàn bộ phần chưa sắp xếp mỗi vòng — khi mảng lớn, điều này dẫn đến nhiều cache miss hơn Insertion Sort (vốn chỉ dịch chuyển cục bộ). Trên CPU hiện đại với cache L1/L2, Insertion Sort thường nhanh hơn Selection Sort cho cùng kích thước input, dù cả hai đều O(n²).
So sánh tổng quan với Bubble Sort và Insertion Sort
| Tiêu chí | Selection | Bubble | Insertion |
|---|---|---|---|
| Best time | Θ(n²) | O(n) | O(n) |
| Worst time | Θ(n²) | O(n²) | O(n²) |
| Swaps | O(n) | O(n²) | O(n²) |
| Stable | ❌ | ✅ | ✅ |
| Adaptive | ❌ | ✅ | ✅ |
| Cache-friendly | ⚠️ Trung bình | ⚠️ Trung bình | ✅ Tốt |
| Ưu thế chính | Ít write nhất | Đơn giản nhất | Nhanh với nearly-sorted |
Kết luận: Selection Sort chỉ thắng khi write cost >> read cost. Trong mọi trường hợp khác, Insertion Sort là lựa chọn tốt hơn trong nhóm O(n²).
Checklist ghi nhớ
✅ Checklist triển khai
Cơ chế cốt lõi
- [ ] Selection Sort chia mảng thành vùng đã sắp xếp (trái) và chưa sắp xếp (phải)
- [ ] Mỗi vòng lặp: quét tìm min trong vùng phải, swap với phần tử đầu vùng phải
- [ ] Sau
n − 1vòng, mảng hoàn toàn có thứ tự
Độ phức tạp
- [ ] Comparisons: luôn Θ(n²) = n(n−1)/2, không có best case nhanh hơn
- [ ] Swaps: tối đa n − 1 = O(n), đây là ưu điểm chính
- [ ] Space: O(1) in-place, chỉ cần một biến tạm
Tính chất quan trọng
- [ ] Không ổn định (unstable) — swap có thể đảo thứ tự tương đối các phần tử bằng nhau
- [ ] Không adaptive — không tận dụng được input đã gần sắp xếp
- [ ] Thích hợp khi chi phí write >> chi phí read (flash, EEPROM, SSD wear leveling)
- [ ] Với dữ liệu thông thường trên RAM, Insertion Sort hầu như luôn tốt hơn
Bài tập luyện tập
Bài 1: Đếm số swap thực tế — Foundation
Đề bài: Cho mảng arr, thực hiện Selection Sort và đếm số lần swap thực sự xảy ra (không tính trường hợp minIdx == i). Trả về mảng đã sắp xếp và số swap.
python
def selection_sort_count(arr: list[int]) -> tuple[list[int], int]:
"""Trả về (mảng đã sort, số swap thực tế)."""
# TODO: Triển khai
pass
# Test cases
assert selection_sort_count([3, 1, 2]) == ([1, 2, 3], 1)
assert selection_sort_count([1, 2, 3]) == ([1, 2, 3], 0)
assert selection_sort_count([5, 4, 3, 2, 1]) == ([1, 2, 3, 4, 5], 2)💡 Gợi ý
- Thêm biến
counttăng mỗi khi swap thực sự xảy ra. - Mảng
[5, 4, 3, 2, 1]chỉ cần 2 swap: swap(5,1) và swap(4,2). Phần tử 3 đã đúng vị trí.
✅ Lời giải
python
def selection_sort_count(arr: list[int]) -> tuple[list[int], int]:
a = arr[:]
n = len(a)
swaps = 0
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
if min_idx != i:
a[i], a[min_idx] = a[min_idx], a[i]
swaps += 1
return a, swapsPhân tích: Time O(n²), Space O(n) do copy mảng. Số swap tối đa n−1, tối thiểu 0.
Bài 2: Selection Sort ổn định — Intermediate
Đề bài: Triển khai phiên bản stable của Selection Sort bằng cách dùng kỹ thuật chèn (insert) thay vì swap. Khi tìm được phần tử nhỏ nhất tại vị trí minIdx, lưu giá trị đó, dịch tất cả phần tử từ i đến minIdx - 1 sang phải một bước, rồi đặt giá trị min vào vị trí i.
python
def stable_selection_sort(arr: list[tuple[int, str]]) -> list[tuple[int, str]]:
"""Selection Sort ổn định cho danh sách tuple (value, label)."""
# TODO: Triển khai
pass
# Test: phần tử cùng value phải giữ nguyên thứ tự gốc
data = [(4, 'a'), (3, 'x'), (4, 'b'), (1, 'y')]
assert stable_selection_sort(data) == [(1, 'y'), (3, 'x'), (4, 'a'), (4, 'b')]💡 Gợi ý
- Thay vì swap
arr[i]vàarr[minIdx], hãy lưuarr[minIdx]vào biến tạm. - Dịch
arr[i..minIdx-1]sang phải một vị trí:arr[k+1] = arr[k]với k từminIdx-1vềi. - Đặt giá trị tạm vào
arr[i]. - Trade-off: Số write tăng từ O(n) lên O(n²).
✅ Lời giải
python
def stable_selection_sort(arr: list[tuple[int, str]]) -> list[tuple[int, str]]:
a = arr[:]
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j][0] < a[min_idx][0]:
min_idx = j
if min_idx != i:
min_val = a[min_idx]
# Dịch các phần tử từ i..minIdx-1 sang phải
for k in range(min_idx, i, -1):
a[k] = a[k - 1]
a[i] = min_val
return aPhân tích: Time O(n²), Space O(n). Stable nhưng mất ưu điểm O(n) write — giờ là O(n²) write do shift. Chỉ dùng khi cần stability và không có lựa chọn khác.
🧠 Quiz
Selection Sort trên mảng [3, 3, 1, 2] — sau vòng lặp đầu tiên, mảng trông như thế nào?
- [ ] A.
[1, 3, 3, 2]— swap3(vị trí 0) với1(vị trí 2) - [x] B.
[1, 3, 3, 2]— đúng, nhưng chú ý: hai phần tử3vẫn giữ vị trí tương đối - [ ] C.
[1, 2, 3, 3]— mảng đã sắp xếp hoàn toàn - [ ] D.
[2, 3, 1, 3]— swap sai phần tử
Giải thích: Vòng 1 tìm min = 1 (vị trí 2), swap với vị trí 0. Kết quả [1, 3, 3, 2]. Đáp án A và B có cùng mảng, nhưng B chính xác hơn vì nhấn mạnh tính chất stability — trong trường hợp này hai phần tử 3 chưa bị đảo, nhưng ở các vòng sau có thể xảy ra (vòng 3: swap 3 vị trí 1 với 2 vị trí 3 → [1, 2, 3, 3], thứ tự 3 bị đảo nếu chúng mang metadata khác nhau).
🎬 Bubble Sort Visualizer
Chưa sắp xếp Đang so sánh Đã sắp xếp
Liên kết học tiếp
Từ khóa glossary: selection sort, sắp xếp chọn, unstable sort, in-place sort, comparison sort, O(n) swaps
Tìm kiếm liên quan: sắp xếp chọn, selection sort là gì, so sánh selection sort bubble sort, thuật toán sắp xếp đơn giản