Thuật toán Python

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

Tìm giá trị nhỏ nhất còn lại và đưa nó lên đầu, lần lượt từng vị trí một.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Vùng đã sắp xếp và vùng chưa sắp xếp
  • Tìm giá trị nhỏ nhất của phần còn lại
  • Vì sao nó luôn cần O(n²) phép so sánh
[64, 25, 12, 22, 11]
11
25
12
22
64
11
12
25
22
64
11
12
22
25
64
Mỗi lượt thêm giá trị nhỏ nhất tiếp theo vào phần đã sắp xếp (tô sáng).

Chọn giá trị nhỏ nhất, đổi chỗ vào

Vấn đề

Một số thuật toán sắp xếp cố di chuyển phần tử càng ít càng tốt. Điều này quan trọng khi mỗi lần di chuyển đều tốn kém. Sắp xếp chọn (selection sort) cho thấy một chiến lược khác với bubble sort: tìm đúng phần tử trước, rồi chỉ di chuyển nó một lần.

Hình dung đời thường

Selection sort giống chọn người vào đội theo chiều cao. Bạn nhìn khắp những người còn đang đợi, gọi người thấp nhất ra và đặt vào chỗ trống tiếp theo trong hàng. Rồi lại nhìn những người còn lại để tìm người thấp nhất kế tiếp, cho tới khi không còn ai.

Từ việc chọn đội đến code
for start in range(len(result)):📍 Chỗ trống tiếp theo trong hàng
minimum = start🤔 Tạm coi người này là thấp nhất
result[index] < result[minimum]🔎 Tìm trong số còn lại xem có ai thấp hơn
result[start], result[minimum] = ...🔄 Đưa người thấp nhất vào chỗ trống
Mỗi vị trí chỉ đổi chỗ một lần, sau khi đã xem hết phần chưa sắp xếp.
Định nghĩa ngắn gọn

Selection sort lặp lại việc tìm phần tử nhỏ nhất trong phần chưa sắp xếp và đổi chỗ để đưa nó vào vị trí tiếp theo của phần đã sắp xếp, tốn O(n²) phép so sánh nhưng chỉ tối đa n - 1 lần đổi chỗ.

Những điểm quan trọng

  1. Mọi thứ bên trái start đã được sắp xếp; từ start trở đi thì chưa.
  2. minimum ghi nhớ vị trí của giá trị nhỏ nhất tìm được cho tới lúc đó trong phần chưa sắp xếp.
  3. Vòng trong for index in range(start + 1, len(result)): duyệt phần còn lại của list.
  4. result[start], result[minimum] = result[minimum], result[start] chỉ đổi chỗ một lần cho mỗi vị trí.

Khi nào nên sử dụng?

  • Học và so sánh các chiến lược sắp xếp.
  • Tình huống mà ghi hoặc di chuyển phần tử tốn kém còn so sánh thì rẻ.
  • Tìm k phần tử nhỏ nhất bằng cách dừng sau k lượt.

Khi nào chưa cần

  • Chương trình thật: sorted() nhanh hơn nhiều.
  • Dữ liệu gần như đã có thứ tự: selection sort vẫn duyệt hết, trong khi insertion sort xong rất nhanh.

Mô phỏng Sắp xếp chọn (selection sort) trong Python

O(n²)

Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.

Code ví dụ

Chạy code →
main.py
def selection_sort(values):
    result = values.copy()
    for start in range(len(result)):
        minimum = start
        for index in range(start + 1, len(result)):
            if result[index] < result[minimum]:
                minimum = index
        result[start], result[minimum] = result[minimum], result[start]
    return result

print(selection_sort([64, 25, 12, 22, 11]))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

[11, 12, 22, 25, 64]

Giải thích code

Biến minimum ghi lại vị trí của giá trị nhỏ nhất trong phần còn lại của danh sách. Sau mỗi lượt duyệt, giá trị đó được đổi chỗ lên vị trí start. Thuật toán luôn có độ phức tạp O(n²) do phải so sánh nhiều lần, nhưng chỉ đổi chỗ tối đa n lần.

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Đổi chỗ ngay trong vòng trong

Làm vậy thì thuật toán thành một kiểu sắp xếp chậm hơn, rối hơn, phải đổi chỗ rất nhiều lần.

Sai
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Cách sửa
for index in range(start + 1, len(result)):
    if result[index] < result[minimum]:
        minimum = index
result[start], result[minimum] = result[minimum], result[start]

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách