Sắp xếp chọn (Selection Sort): giải thích từng bước, so sánh với Insertion Sort và code C++, Python

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Sắp xếp chọn (Selection Sort): trả về số lần hoán đổi thực sự (khi min_idx != i)
int selection_sort(vector<int>& a) {
    int n = (int)a.size();
    int so_lan_swap = 0;
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            swap(a[i], a[min_idx]);
            ++so_lan_swap;
        }
    }
    return so_lan_swap;
}

void in_ket_qua(const vector<int>& a, int so_lan_swap) {
    cout << "Swaps: " << so_lan_swap << " | Mang: ";
    for (int i = 0; i < (int)a.size(); ++i) {
        cout << a[i] << (i + 1 == (int)a.size() ? "" : " ");
    }
    cout << "\n";
}

int main() {
    // Test 1: Mảng ví dụ trong bài [64, 25, 12, 22, 11]
    vector<int> a1 = {64, 25, 12, 22, 11};
    int s1 = selection_sort(a1);
    in_ket_qua(a1, s1); // Swaps: 3 | Mang: 11 12 22 25 64

    // Test 2: Mảng đã tăng dần sẵn -> 0 lần swap (nhưng vẫn chạy đủ phép so sánh)
    vector<int> a2 = {3, 7, 11, 15};
    int s2 = selection_sort(a2);
    in_ket_qua(a2, s2); // Swaps: 0 | Mang: 3 7 11 15

    // Test 3: Mảng có phần tử âm và trùng nhau
    vector<int> a3 = {5, -3, 5, 0, -8};
    int s3 = selection_sort(a3);
    in_ket_qua(a3, s3); // Swaps: 2 | Mang: -8 -3 0 5 5

    return 0;
}

def selection_sort(a: list[int]) -> int:
    """Sắp xếp chọn (Selection Sort): trả về số lần hoán đổi thực sự (khi min_idx != i)."""
    n = len(a)
    so_lan_swap = 0
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]
            so_lan_swap += 1
    return so_lan_swap


def in_ket_qua(a: list[int], so_lan_swap: int) -> None:
    print(f"Swaps: {so_lan_swap} | Mang: {' '.join(map(str, a))}")


if __name__ == "__main__":
    # Test 1: Mảng ví dụ trong bài [64, 25, 12, 22, 11]
    a1 = [64, 25, 12, 22, 11]
    s1 = selection_sort(a1)
    in_ket_qua(a1, s1)  # Swaps: 3 | Mang: 11 12 22 25 64

    # Test 2: Mảng đã tăng dần sẵn -> 0 lần swap (nhưng vẫn chạy đủ phép so sánh)
    a2 = [3, 7, 11, 15]
    s2 = selection_sort(a2)
    in_ket_qua(a2, s2)  # Swaps: 0 | Mang: 3 7 11 15

    # Test 3: Mảng có phần tử âm và trùng nhau
    a3 = [5, -3, 5, 0, -8]
    s3 = selection_sort(a3)
    in_ket_qua(a3, s3)  # Swaps: 2 | Mang: -8 -3 0 5 5

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Đếm số phép ghi vào mảng a[...] của Selection Sort (mỗi lần swap ghi 2 ô nhớ)
int ghi_selection(vector<int> a) {
    int n = (int)a.size(), ghi = 0;
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[min_idx]) min_idx = j;
        }
        if (min_idx != i) {
            swap(a[i], a[min_idx]);
            ghi += 2;
        }
    }
    return ghi;
}

// Đếm số phép ghi vào mảng a[...] của Insertion Sort
int ghi_insertion(vector<int> a) {
    int n = (int)a.size(), ghi = 0;
    for (int i = 1; i < n; ++i) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
            ++ghi;
        }
        if (j + 1 != i) {
            a[j + 1] = key;
            ++ghi;
        }
    }
    return ghi;
}

// Đếm số phép ghi vào mảng a[...] của Bubble Sort (mỗi lần swap ghi 2 ô nhớ)
int ghi_bubble(vector<int> a) {
    int n = (int)a.size(), ghi = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                ghi += 2;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return ghi;
}

int main() {
    vector<vector<int>> cac_mang = {
        {64, 25, 12, 22, 11},  // Mảng ví dụ 5 phần tử
        {6, 5, 4, 3, 2, 1},    // Mảng giảm dần 6 phần tử
        {1, 2, 3, 4, 5, 6}     // Mảng đã tăng dần
    };

    for (const auto& a : cac_mang) {
        cout << "Selection: " << ghi_selection(a)
             << " | Insertion: " << ghi_insertion(a)
             << " | Bubble: " << ghi_bubble(a) << "\n";
    }
    return 0;
}

def ghi_selection(mang_goc: list[int]) -> int:
    """Đếm số phép ghi vào mảng a[...] của Selection Sort (mỗi swap ghi 2 ô)."""
    a = mang_goc[:]
    n, ghi = len(a), 0
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        if min_idx != i:
            a[i], a[min_idx] = a[min_idx], a[i]
            ghi += 2
    return ghi


def ghi_insertion(mang_goc: list[int]) -> int:
    """Đếm số phép ghi vào mảng a[...] của Insertion Sort."""
    a = mang_goc[:]
    n, ghi = len(a), 0
    for i in range(1, n):
        key, j = a[i], i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
            ghi += 1
        if j + 1 != i:
            a[j + 1] = key
            ghi += 1
    return ghi


def ghi_bubble(mang_goc: list[int]) -> int:
    """Đếm số phép ghi vào mảng a[...] của Bubble Sort (mỗi swap ghi 2 ô)."""
    a = mang_goc[:]
    n, ghi = len(a), 0
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                ghi += 2
                swapped = True
        if not swapped:
            break
    return ghi


if __name__ == "__main__":
    cac_mang = [
        [64, 25, 12, 22, 11],  # Mảng ví dụ 5 phần tử
        [6, 5, 4, 3, 2, 1],    # Mảng giảm dần 6 phần tử
        [1, 2, 3, 4, 5, 6],    # Mảng đã tăng dần
    ]

    for a in cac_mang:
        print(
            f"Selection: {ghi_selection(a)} | "
            f"Insertion: {ghi_insertion(a)} | "
            f"Bubble: {ghi_bubble(a)}"
        )