Sắp xếp chọn (selection sort) trong Python
Bài 15/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 8 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp chọn (selection sort) là thuật toán sắp xếp mà mỗi lượt tìm phần tử nhỏ nhất trong phần chưa xếp rồi đưa nó lên đầu phần đó bằng đúng một lần đổi chỗ. Bạn dùng cách này khi muốn ít lần đổi chỗ, ví dụ xếp độ dài các tuyến xe trên bản đồ từ ngắn tới dài mà không đảo qua đảo lại nhiều lần.
Cần biết trước: sắp xếp nổi bọt và vòng lặp lồng nhau.
Tìm phần tử nhỏ nhất của một lượt
Bản đồ ghi độ dài (km) năm tuyến xe: [18, 7, 25, 7, 12]. Lượt đầu cần biết tuyến ngắn nhất nằm ở chỉ số nào. Bạn giữ chỉ số của số nhỏ nhất đã thấy trong biến vi_tri_min, rồi đi qua các phần tử còn lại, gặp số nhỏ hơn thì nhớ chỉ số mới:
do_dai = [18, 7, 25, 7, 12]
vi_tri_min = 0
for j in range(1, len(do_dai)):
if do_dai[j] < do_dai[vi_tri_min]:
vi_tri_min = j
print("Nhỏ nhất:", do_dai[vi_tri_min], "ở chỉ số", vi_tri_min)
do_dai[0], do_dai[vi_tri_min] = do_dai[vi_tri_min], do_dai[0]
print(do_dai)KẾT QUẢ
Nhỏ nhất: 7 ở chỉ số 1
[7, 18, 25, 7, 12]Vòng lặp chỉ ghi nhớ chỉ số, chưa đổi chỗ gì. Hết vòng mới có một lần đổi chỗ đưa 7 về chỉ số 0. Hai tuyến cùng dài 7 km, và phép so hẳn < giữ tuyến gặp trước ở chỉ số 1. Đổi < thành <= rồi chạy lại: dòng đầu in ở chỉ số 3.
Viết selection sort bằng hai vòng lặp
Sau lượt đầu, chỉ số 0 đã đúng chỗ. Lượt có chỉ số i lặp lại việc trên cho phần từ i tới cuối: bắt đầu với vi_tri_min = i, vòng trong chạy từ i + 1. Giống người xếp hàng theo chiều cao, mỗi lần gọi người thấp nhất trong số còn lại bước lên đứng kế tiếp:
def selection_sort(ds):
ds = ds.copy()
n = len(ds)
for i in range(n - 1):
vi_tri_min = i
for j in range(i + 1, n):
if ds[j] < ds[vi_tri_min]:
vi_tri_min = j
ds[i], ds[vi_tri_min] = ds[vi_tri_min], ds[i]
print("Lượt", i + 1, ds)
return ds
print(selection_sort([18, 7, 25, 7, 12]))KẾT QUẢ
Lượt 1 [7, 18, 25, 7, 12]
Lượt 2 [7, 7, 25, 18, 12]
Lượt 3 [7, 7, 12, 18, 25]
Lượt 4 [7, 7, 12, 18, 25]
[7, 7, 12, 18, 25]Phần đầu list lớn dần một phần tử sau mỗi lượt và không bao giờ bị đụng lại. Ngược với sắp xếp nổi bọt, nơi số lớn trôi dần về cuối, ở đây số nhỏ được chọn rồi đặt thẳng vào chỗ. Ở lượt 4, 18 đã nằm đúng chỗ nên phép đổi chỗ đổi 18 với chính nó.
Đếm số phép so sánh và số lần đổi chỗ
Lượt có chỉ số i so n - 1 - i lần, dù list đã xếp hay chưa, nên tổng luôn là n * (n - 1) // 2. Số lần đổi chỗ thì khác: nếu chỉ đổi khi vi_tri_min khác i, mỗi lượt đổi nhiều nhất một lần:
def dem(ds):
ds = ds.copy()
so_sanh, so_doi = 0, 0
for i in range(len(ds) - 1):
vi_tri_min = i
for j in range(i + 1, len(ds)):
so_sanh += 1
if ds[j] < ds[vi_tri_min]:
vi_tri_min = j
if vi_tri_min != i:
ds[i], ds[vi_tri_min] = ds[vi_tri_min], ds[i]
so_doi += 1
return so_sanh, so_doi
print(dem(list(range(1, 11))), dem(list(range(10, 0, -1))))KẾT QUẢ
(45, 0) (45, 5)List mười số đã tăng dần và list xếp ngược đều tốn 45 phép so sánh. Sắp xếp chọn không có cách nào biết list đã xếp sẵn, nên không dừng sớm được như bubble sort có biến cờ. Bù lại, list xếp ngược chỉ tốn năm lần đổi chỗ, trong khi bubble sort phải đổi chỗ 45 lần, mỗi cặp số đứng ngược thứ tự một lần. Khi mỗi lần ghi vào list tốn kém, như ghi lên bộ nhớ chậm, ít lần đổi chỗ là lợi thế thật. Độ phức tạp vẫn là O(n²) theo cách đếm của bài Big O.
Sắp xếp chọn không ổn định
Một lần đổi chỗ có thể đẩy một phần tử ở đầu ra sau một phần tử bằng nó. Xếp ba tuyến theo độ dài, tuyến 01 và tuyến 08 cùng dài 12 km:
def xep_theo_km(cac_tuyen):
ds = cac_tuyen.copy()
for i in range(len(ds) - 1):
vi_tri_min = i
for j in range(i + 1, len(ds)):
if ds[j][1] < ds[vi_tri_min][1]:
vi_tri_min = j
ds[i], ds[vi_tri_min] = ds[vi_tri_min], ds[i]
return ds
cac_tuyen = [("Tuyến 01", 12), ("Tuyến 08", 12), ("Tuyến 15", 5)]
print(xep_theo_km(cac_tuyen))KẾT QUẢ
[('Tuyến 15', 5), ('Tuyến 08', 12), ('Tuyến 01', 12)]Lượt đầu đổi chỗ tuyến 01 với tuyến 15 ở cuối list, nên tuyến 01 nhảy qua tuyến 08. Phép so < không cứu được trường hợp này, vì lỗi nằm ở lần đổi chỗ xa chứ không ở phép so. Sắp xếp chọn vì vậy không ổn định, khác với bubble sort. Cần giữ thứ tự gặp trước của các phần tử bằng nhau thì dùng sorted() với key= hay một thuật toán ổn định, như bài thuật toán sắp xếp so sánh.
Kiểm tra nhanh
Trong ví dụ tìm phần tử nhỏ nhất đầu bài, đổi list thành
[9, 4, 6, 4]thì dòng đầu in ra gì?Nhỏ nhất: 4 ở chỉ số 1Nhỏ nhất: 4 ở chỉ số 3Nhỏ nhất: 9 ở chỉ số 0
Với list
nphần tử, những điều nào đúng với hàmdemcủa bài?- Luôn làm
n * (n - 1) // 2phép so sánh, kể cả khi list đã xếp sẵn - Dừng sau một lượt khi list đã xếp sẵn
- Đổi chỗ nhiều nhất
n - 1lần - Giữ nguyên thứ tự của hai tuyến cùng độ dài
- Luôn làm
Lượt có
i = 0viết nhầmif ds[j] < ds[i]:thay choif ds[j] < ds[vi_tri_min]:. Vớids = [18, 7, 25, 7, 12], hết vòng trongvi_tri_minbằng bao nhiêu?- 1
- 3
- 4
Đầu mỗi lượt viết
vi_tri_min = 0thay chovi_tri_min = i. Chạy hàm trên[18, 7, 25, 7, 12]thì sao?- Báo lỗi IndexError ở lượt cuối
- Kết quả sai, vì số đã xếp ở chỉ số
0bị đổi chỗ ra khỏi đầu list - Kết quả đúng, chỉ tốn thêm một phép so sánh mỗi lượt
Bài tập
Xếp tuyến xe và đếm bước của sắp xếp chọn
List do_dai ghi độ dài (km) các tuyến xe. Viết thân hàm chon_va_dem(do_dai) xếp tăng dần bằng selection sort. Lượt có chỉ số i tìm vị trí số nhỏ nhất từ chỉ số i tới cuối, hai số bằng nhau thì giữ số đứng trước. Sau đó đổi chỗ nó với phần tử ở chỉ số i, chỉ khi hai vị trí khác nhau. Đếm số phép so sánh hai phần tử và số lần đổi chỗ. Tự tìm số nhỏ nhất bằng vòng lặp: không dùng min(), max(), index(), sorted() hay sort(), và không sửa do_dai.
Ví dụ: chon_va_dem([18, 7, 25, 7, 12]) trả về ([7, 7, 12, 18, 25], 10, 3).
Trả về: list đã xếp, số phép so sánh và số lần đổi chỗ, một tuple.
def chon_va_dem(do_dai):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Mỗi lượt sắp xếp chọn tìm chỉ số của số nhỏ nhất trong phần chưa xếp, rồi đổi chỗ nó lên đầu phần đó.
Lượt có chỉ số
ibắt đầu vớivi_tri_min = ivà so với số nhỏ nhất đang giữ, không so vớids[i].Số phép so sánh luôn là
n * (n - 1) // 2, kể cả với list đã xếp, nên thuật toán là O(n²) và không dừng sớm.Chỉ đổi khi
vi_tri_minkhácithì cả thuật toán đổi chỗ nhiều nhấtn - 1lần.Lần đổi chỗ xa có thể đẩy một phần tử qua phần tử bằng nó, nên sắp xếp chọn không ổn định.
Câu hỏi thường gặp
Thuật toán sắp xếp chọn có độ phức tạp bao nhiêu?
Luôn là O(n²) phép so sánh, vì mỗi lượt phải đi hết phần chưa xếp mới biết số nào nhỏ nhất, dù list đã xếp sẵn. Số lần đổi chỗ là O(n), và bộ nhớ thêm là O(1) vì thuật toán xếp tại chỗ. Muốn xem lại O(n) và O(n²) đọc thế nào, mở bài Big O.
Viết selection sort trong Python có giữ thứ tự các phần tử bằng nhau không?
Không, bản đổi chỗ như bài viết không ổn định: lần đổi chỗ xa có thể đẩy một phần tử ra sau phần tử bằng nó. Khi cần ổn định, dùng sorted() với key=, vốn ổn định, hoặc sắp xếp nổi bọt với phép so hẳn >.
Khi nào sắp xếp chọn hợp hơn sắp xếp nổi bọt?
Khi mỗi lần ghi vào dãy tốn kém hơn nhiều so với một phép so sánh, vì sắp xếp chọn đổi chỗ nhiều nhất n - 1 lần. Khi list thường đã gần đúng thứ tự thì bubble sort có biến cờ, hay sắp xếp chèn, nhanh hơn vì dừng hoặc chèn sớm.
Có cách nào lấy số nhỏ nhất nhanh hơn ở mỗi lượt không?
Có: cấu trúc heap đưa số nhỏ nhất ra trong O(log n) thay cho O(n), và bài heapq dạy cách dùng nó.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.