Khái niệm
Sắp xếp chọn (selection sort) chia dãy thành hai phần: phần đã sắp xếp (bên trái) và phần chưa sắp xếp (bên phải). Mỗi lượt tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đặt nó vào cuối phần đã sắp xếp.
- Độ phức tạp thời gian: O(n²) — luôn luôn, không có trường hợp tốt hơn
- Độ phức tạp không gian: O(1) — sắp xếp tại chỗ
- Ổn định: Không — phần tử có thể nhảy qua phần tử bằng nhau
Ưu điểm nổi bật: số lần đổi chỗ tối thiểu — chỉ O(n) lần đổi chỗ, phù hợp khi chi phí ghi bộ nhớ lớn.
Minh hoạ từng bước
Ví dụ sắp xếp [64, 25, 12, 22, 11]:
Bước 1: Tìm min [64,25,12,22,11] → 11, đổi với 64 → [11, 25, 12, 22, 64]
Bước 2: Tìm min [25,12,22,64] → 12, đổi với 25 → [11, 12, 25, 22, 64]
Bước 3: Tìm min [25,22,64] → 22, đổi với 25 → [11, 12, 22, 25, 64]
Bước 4: Tìm min [25,64] → 25, đổi với 25 → [11, 12, 22, 25, 64]
Cài đặt cơ bản
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Tìm vị trí phần tử nhỏ nhất trong arr[i..n-1]
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Đổi chỗ với phần tử ở vị trí i
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
data = [64, 25, 12, 22, 11]
print(selection_sort(data)) # [11, 12, 22, 25, 64]
Bài tập luyện tập
Dễ — Sắp xếp và hiển thị từng bước
In trạng thái dãy sau mỗi lần đổi chỗ để thấy quá trình sắp xếp.
def selection_sort_with_steps(arr):
arr = arr[:]
n = len(arr)
for i in range(n):
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]
print(f" Đổi vị trí {i} và {min_idx}: {arr}")
return arr
print("Bắt đầu: [64, 25, 12, 22, 11]")
selection_sort_with_steps([64, 25, 12, 22, 11])
Trung bình — K phần tử nhỏ nhất
Tìm k phần tử nhỏ nhất trong dãy, không cần sắp xếp toàn bộ.
def k_phan_tu_nho_nhat(arr, k):
"""Tìm k phần tử nhỏ nhất. Dừng sớm sau k lượt chọn."""
arr = arr[:]
n = len(arr)
k = min(k, n)
for i in range(k):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr[:k]
data = [7, 2, 5, 1, 8, 3, 9, 4, 6]
print(k_phan_tu_nho_nhat(data, 3)) # [1, 2, 3]
print(k_phan_tu_nho_nhat(data, 5)) # [1, 2, 3, 4, 5]
Khó — Sắp xếp danh sách đối tượng theo tiêu chí
Sắp xếp danh sách học sinh theo điểm tăng dần, nếu bằng điểm thì xếp theo tên.
def sap_xep_hoc_sinh(hoc_sinh):
"""
hoc_sinh: list of [ten, diem]
Sắp xếp tăng dần theo điểm, nếu bằng thì theo tên alphabet.
"""
n = len(hoc_sinh)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
ten_j, diem_j = hoc_sinh[j]
ten_min, diem_min = hoc_sinh[min_idx]
if diem_j < diem_min or (diem_j == diem_min and ten_j < ten_min):
min_idx = j
hoc_sinh[i], hoc_sinh[min_idx] = hoc_sinh[min_idx], hoc_sinh[i]
return hoc_sinh
ds = [["Minh", 8], ["An", 9], ["Bao", 8], ["Cuong", 7]]
for ten, diem in sap_xep_hoc_sinh(ds):
print(f" {ten}: {diem}")
# Cuong: 7
# Bao : 8
# Minh : 8
# An : 9
Kết luận
Selection sort tốt khi số lần ghi (đổi chỗ) cần tối thiểu. Trong các bài thi, bạn sẽ hiếm khi dùng selection sort trực tiếp — hãy tiếp tục học Sắp xếp chèn và Sắp xếp trộn để có thêm công cụ mạnh hơn.
Bình luận