Sắp xếp chọn

7.1 Định nghĩa sắp xếp chọn

Sắp xếp chọn (Selection Sort) là một thuật toán sắp xếp, tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của mảng và đổi chỗ nó với phần tử đầu tiên của phần đó. Quá trình này lặp lại với các phần tử còn lại cho đến khi toàn bộ mảng được sắp xếp.

Nguyên lý hoạt động:

1. Bắt đầu từ phần tử đầu tiên của mảng.
2. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp còn lại của mảng.
3. Đổi chỗ phần tử nhỏ nhất với phần tử đầu tiên của phần chưa sắp xếp.
4. Lặp lại quá trình cho phần tử tiếp theo cho đến khi toàn bộ mảng được sắp xếp.

Quá trình từng bước

1. Tìm phần tử nhỏ nhất trong mảng và đổi chỗ nó với phần tử đầu tiên.
2. Lặp lại quá trình cho phần mảng còn lại (bắt đầu từ phần tử thứ hai).
3. Tiếp tục quá trình cho đến khi toàn bộ mảng được sắp xếp.

Độ phức tạp về thời gian và không gian của sắp xếp chọn

Độ phức tạp về thời gian:

• Trường hợp xấu nhất: O(n^2) — xảy ra khi các phần tử ban đầu được sắp xếp theo thứ tự ngược lại hoặc ngẫu nhiên.
• Trường hợp trung bình: O(n^2) — xảy ra với sự sắp xếp ngẫu nhiên của các phần tử.
• Trường hợp tốt nhất: O(n^2) — ngay cả khi mảng đã được sắp xếp, thuật toán vẫn thực hiện các so sánh như nhau.

Độ phức tạp về không gian:

O(1) — vì thuật toán sử dụng một lượng bộ nhớ bổ sung cố định (chỉ vài biến để lưu trữ giá trị tạm thời).

7.2 Triển khai thuật toán sắp xếp chọn

Triển khai thuật toán rất đơn giản:

Bước 1: tìm phần tử nhỏ nhất trong tất cả các phần tử và đổi chỗ nó với phần tử đầu tiên.

Bước 2: tìm phần tử nhỏ nhất trong tất cả các phần tử, ngoại trừ phần tử đầu tiên, và đổi chỗ nó với phần tử thứ hai.

Bước 3: tìm phần tử nhỏ nhất trong tất cả các phần tử, ngoại trừ phần tử đầu tiên và thứ hai, và đổi chỗ nó với phần tử thứ ba.

Triển khai bằng Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Tìm phần tử nhỏ nhất trong phần còn lại chưa được sắp xếp của mảng
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Đổi chỗ phần tử nhỏ nhất tìm được với phần tử đầu tiên của phần chưa sắp xếp
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # Trả về mảng đã được sắp xếp

# Ví dụ sử dụng:
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Mảng đã sắp xếp:", sorted_arr)
# Kết quả: Mảng đã sắp xếp: [11, 12, 22, 25, 64]

Ví dụ hoạt động của thuật toán:

1. Lần chạy đầu tiên (i = 0):
   1. Tìm phần tử nhỏ nhất (11) trong phần chưa được sắp xếp của mảng [64, 25, 12, 22, 11].
   2. Đổi chỗ 11 với 64.
   3. Mảng: [11, 25, 12, 22, 64]
2. Lần chạy thứ hai (i = 1):
   1. Tìm phần tử nhỏ nhất (12) trong phần chưa được sắp xếp của mảng [25, 12, 22, 64].
   2. Đổi chỗ 12 với 25.
   3. Mảng: [11, 12, 25, 22, 64]
3. Lần chạy thứ ba (i = 2):
   1. Tìm phần tử nhỏ nhất (22) trong phần chưa được sắp xếp của mảng [25, 22, 64].
   2. Đổi chỗ 22 với 25.
   3. Mảng: [11, 12, 22, 25, 64]
4. Lần chạy thứ tư (i = 3):
   1. Tìm phần tử nhỏ nhất (25) trong phần chưa được sắp xếp của mảng [25, 64].
   2. 25 đã ở đúng vị trí, không cần đổi chỗ.
   3. Mảng: [11, 12, 22, 25, 64]

Thuật toán kết thúc vì tất cả các phần tử đã được sắp xếp.