Bỏ qua đến nội dung chính
Mục lục

Sắp xếp chọn (selection sort) trong Python

AIDev Team · duyệt: Nguyễn Việt Chung

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

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:

python
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:

python
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:

python
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:

python
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

  1. 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ố 1
    • Nhỏ nhất: 4 ở chỉ số 3
    • Nhỏ nhất: 9 ở chỉ số 0
  2. Với list n phần tử, những điều nào đúng với hàm dem của bài?

    • Luôn làm n * (n - 1) // 2 phé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 - 1 lần
    • Giữ nguyên thứ tự của hai tuyến cùng độ dài
  3. Lượt có i = 0 viết nhầm if ds[j] < ds[i]: thay cho if ds[j] < ds[vi_tri_min]:. Với ds = [18, 7, 25, 7, 12], hết vòng trong vi_tri_min bằng bao nhiêu?

    • 1
    • 3
    • 4
  4. Đầu mỗi lượt viết vi_tri_min = 0 thay cho vi_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ố 0 bị đổ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
Đúng hết lần đầu +15 XP

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.

python
def chon_va_dem(do_dai):
    pass  # Viết thân hàm thay cho dòng này

Tó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ố i bắt đầu với vi_tri_min = i và so với số nhỏ nhất đang giữ, không so với ds[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_min khác i thì cả thuật toán đổi chỗ nhiều nhất n - 1 lầ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ủ đề

selection sort

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập