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

Phân loại: Giải thuật sắp xếp ổn định.

Cấu trúc dữ liệu: Ngẫu nhiên.

Độ phức tạp thời gian (Time Complexity): Trường hợp xấu nhất (Worst Case) O(n²).

Độ phức tạp dung lượng (Space Complexity): O(1).

Độ phức tạp bộ nhớ (Memory Complexity): O(1).

Cách hoạt động:

1. Tìm phần tử nhỏ nhất trong phần chưa sắp xếp.
2. Hoán đổi phần tử nhỏ nhất đó với phần tử đầu tiên của phần chưa sắp xếp.
3. Di chuyển ranh giới giữa phần đã sắp xếp và phần chưa sắp xếp một phần tử sang phải.

Pseudocode:

function selectionSort(arr):
    n = length(arr)
    for i from 0 to n-1:
        // Tìm phần tử nhỏ nhất trong phần chưa được sắp xếp
        minIndex = i
        for j from i+1 to n-1:
            if arr[j] < arr[minIndex]:
                minIndex = j
        // Hoán đổi phần tử nhỏ nhất tìm được với phần tử đầu tiên của phần chưa được sắp xếp
        if minIndex != i:
            swap(arr[i], arr[minIndex])
    return arr

Code C++:

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        // Tìm phần tử nhỏ nhất trong phần chưa sắp xếp
        int minIndex = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Hoán đổi 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
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

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