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

Ý tưởng chính là tìm phần tử nhỏ nhất trong mảng, đưa nó về đúng vị trí và lặp lại cho đến khi mảng được sắp xếp xong.

Nguyên lý hoạt động

- Duyệt qua mảng, tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp.

- Hoán đổi phần tử nhỏ nhất đó với phần tử đầu tiên trong của đoạn chưa sắp xếp.

- Lặp lại cho đến khi toàn bộ mảng được sắp xếp.

Ví dụ: Mảng [64, 25, 12, 22, 11]
- lần 1: Tìm min = 11, đổi chổ với 64 - [11, 25, 12, 22, 64]
- lần 2: Tìm min = 12, đổi chổ với 25 - [11, 12, 25, 22, 64]
- lần 3: Tìm min = 22, đổi chổ với 25 - [11, 12, 22, 25, 64]
- lần 4: Tìm min = 25, đổi chổ với chính nó - [11, 12, 22, 25, 64]
- Mảng đã được sắp xếp tăng dần.

Code Python

def selection_sort(arr):
    n = len(arr)						    # Lấy độ dài mảng
    for i in range(n-1):					    # Duyệt qua từng phần tử mảng
    	min_index = i						    # Giả đinh i là phần tử nhỏ nhất
        # TÌm phần tử nhỏ nhất trong đoạn chưa sắp xếp
        for j in range(i+1, n):					    # Duệt từ i đến hết đoạn chưa sắp xếp
        	if arr[j] < arr[min_index]:			    # Nếu j nhỏ hơn min_index
        		min_index = j				    # Thì min_index chính là j
        # Hoán đổi phần tử nhỏ nhất với phần tử đầu tiên của đoạn
        arr[i], arr[min_index] = arr[min_index], arr[i]		    # Hoán đổi vị trí phần tử nhỏ nhất

Giải thích

- Vòng lặp ngoài chọn vị trí hiện tại i.

- Vòng lặp trong tìm phần tử nhỏ nhất từ i+1 đến hết mảng.

- Hoán đổi phần tử nhỏ nhất với phần tử hiện tại i.

- Lặp lại cho đến khi mảng được sắp xếp xong.

Code C++

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = 0; j < n-1; j++) {
            if (arr[j] < arr[mindIndex]) {
            	minIndex = j;
            }
        }
        swap(arr[minIndex], arr[i]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
    	cout << arr[i] << " ";
    return 0;
}

Ưu và nhược điểm

- Ưu điểm:
+ Đơn giản, dễ hiểu: Ý tưởng trực quan, dễ cài đặt và dễ giải thíchcho người mới học.
+ Ít hoán đổi: Mỗi vòng lặp chỉ thực hiện một lần hoán đổi, nên số lần hoán đổi ít hơn so với Bubble Sort.
+ Không cần bộ nhớ bổ sung: Là thuật toán in-plance, chỉ cần hoán đổi trong mảng gốc, không dùng mảng phụ.
+ Ứng dụng trong giáo dục: Rất phổ biến để giảng khái niệm về thuật toán sắp xếp.

- Nhược điểm:
+ Độ phức tạp thời gian cao: Xử lý chậm cho tất cả trường hợp.
+ Không ổn định: Có thể làm thay đổi vị trí tương đối của các phần tử bằng nhau.
+ Không phù hợp cho dữ liệu lớn: Khi số phần tử tăng, thời gian xử lý tăng nhanh, kém hiệu quả so.

Ứng dụng

- Giáo dục và minh họa: Dùng để giảng dạy nguyên lý sắp xếp.

- Kiểm tra và gỡ lỗi: Có thể dùng như một thuật toán tham chiếu đơn giản để kiểm tra sinh đúng đắn của các thuật toán sắp xếp phức tạp hơn.

- Xử lý mảng nhỏ: Khi dữ liệu ít và yêu cầu bộ nhớ thấp, Selection Sort vẫn có thể được áp dụng.