Thuật toán sắp xếp chọn (Selection sort)

Thuật toán sắp xếp chọn (Selection sort) là thuật toán sắp xếp đơn giản nhất trong các thuật toán sắp xếp cơ bản. Cách thức hoạt động của thuật toán này như sau:

1. Tìm phần tử nhỏ nhất trong danh sách.
2. Đưa phần tử nhỏ nhất này về vị trí đầu tiên của danh sách.
3. Lặp lại quá trình trên với danh sách còn lại cho đến khi danh sách được sắp xếp hoàn toàn.

Độ phức tạp của thuật toán sắp xếp chọn (Selection sort) là O(n^2), tương đương với thuật toán sắp xếp nổi bọt (Bubble Sort). Tuy nhiên, Selection Sort thường hiệu quả hơn Bubble Sort do có ít hoán đổi hơn.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp chọn:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Tìm phần tử nhỏ nhất trong danh sách chưa sắp xếp
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Đưa phần tử nhỏ nhất về đầu danh sách chưa sắp xếp
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp chọn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]