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.
- 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
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.
for start in range(len(result)):📍 Chỗ trống tiếp theo trong hàngminimum = start🤔 Tạm coi người này là thấp nhấtresult[index] < result[minimum]🔎 Tìm trong số còn lại xem có ai thấp hơnresult[start], result[minimum] = ...🔄 Đưa người thấp nhất vào chỗ trốngSelection 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
- Mọi thứ bên trái
startđã được sắp xếp; từstarttrở đi thì chưa. minimumghi 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.- Vòng trong
for index in range(start + 1, len(result)):duyệt phần còn lại của list. 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ụ
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]))
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.
- 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.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đ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.
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.
for index in range(start + 1, len(result)):
if result[index] < result[start]:
result[start], result[index] = result[index], result[start]
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.
- Giá trị nhỏ nhất trong mảng Tìm giá trị nhỏ nhất trong một danh sách. Dễ
- K-th Smallest Element Find the k-th smallest value without fully sorting. Trung bình