Nhóm Thuật Toán
Sắp Xếp Cơ Bản Trên Mảng

#include <bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        // Dịch các phần tử > key sang phải
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // Chèn key vào vị trí đúng
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    insertionSort(a);

    for (int x : a) cout << x << " ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void selectionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;

        // Tìm phần tử nhỏ nhất trong [i+1..n-1]
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[minIdx]) {
                minIdx = j;
            }
        }

        // Hoán đổi (đây là lý do UNSTABLE!)
        if (minIdx != i) {
            swap(a[i], a[minIdx]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    selectionSort(a);

    for (int x : a) cout << x << " ";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

void countingSort(vector<int>& a) {
    if (a.empty()) return;

    int maxVal = *max_element(a.begin(), a.end());
    vector<int> count(maxVal + 1, 0);

    // Bước 1: Đếm tần suất
    for (int x : a) {
        count[x]++;
    }

    // Bước 2: Ghi lại theo thứ tự
    int idx = 0;
    for (int val = 0; val <= maxVal; val++) {
        while (count[val] > 0) {
            a[idx++] = val;
            count[val]--;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    countingSort(a);

    for (int x : a) cout << x << " ";
    return 0;
}