Selection Sort (Sắp Xếp Chọn)

Selection Sort hoạt động theo nguyên lý "chọn lọc tinh hoa": liên tục tìm phần tử nhỏ nhất từ phần chưa sắp xếp và đưa nó về đầu.

Cơ Chế Hoạt Động

Giải thuật chia mảng thành hai phần:

1. Phần đã sắp xếp (bên trái).
2. Phần chưa sắp xếp (bên phải).

Ở mỗi bước, ta tìm min_index trong phần chưa sắp xếp và hoán đổi nó với phần tử đầu tiên của phần này.

🎬 Bubble Sort Visualizer

64

34

25

12

22

11

90

45

67

30

Chưa sắp xếp Đang so sánh Đã sắp xếp

Giải Thích Chi Tiết

Mảng ban đầu: [64, 25, 12, 22, 11]

1. Pass 1:

   • Tìm min trong [64, 25, 12, 22, 11]. Min là 11.
   • Swap 11 với 64 (vị trí đầu tiên).
   • Mảng: [11, 25, 12, 22, 64] (11 đã sort).

2. Pass 2:

   • Tìm min trong [25, 12, 22, 64]. Min là 12.
   • Swap 12 với 25.
   • Mảng: [11, 12, 25, 22, 64] (11, 12 đã sort).

3. Pass 3:

   • Tìm min trong [25, 22, 64]. Min là 22.
   • Swap 22 với 25.
   • Mảng: [11, 12, 22, 25, 64].

Code Implementation

C++

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // Tìm phần tử nhỏ nhất trong mảng chưa sắp xếp
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        // Hoán đổi phần tử nhỏ nhất tìm được với phần tử đầu tiên
        swap(arr[min_idx], arr[i]);
    }
}

Java

class SelectionSort {
    void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            }
            // Swap
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

⚠️ HPN's Note

Mặc dù Selection Sort luôn chạy với độ phức tạp O(N²) (kể cả khi mảng đã sort sẵn), nhưng nó có một ưu điểm đặc biệt: Số lần ghi vào bộ nhớ (write) là tối thiểu (tối đa O(N) lần hoán đổi). Điều này hữu ích khi chi phí ghi vào bộ nhớ flash (EEPROM) là rất đắt đỏ.