Sắp xếp chèn (Insertion Sort): giải thích từng bước, tối ưu dịch phần tử và code C++, Python

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

// Sắp xếp chèn chuẩn: dùng biến tạm key và phép dịch phải, trả về tổng số lần dịch
long long insertion_sort(vector<int>& a) {
    int n = (int)a.size();
    long long so_lan_dich = 0;
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        // Dịch các phần tử trong đoạn [0 .. i-1] lớn hơn key sang phải 1 vị trí
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
            ++so_lan_dich;
        }
        a[j + 1] = key; // Đặt key vào đúng khe trống
    }
    return so_lan_dich;
}

void in_ket_qua(const vector<int>& a, long long so_lan_dich) {
    cout << "Dich: " << so_lan_dich << " | 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 [7, 3, 5, 2, 6]
    vector<int> a1 = {7, 3, 5, 2, 6};
    long long d1 = insertion_sort(a1);
    in_ket_qua(a1, d1); // Dich: 6 | Mang: 2 3 5 6 7

    // Test 2: Mảng gần như đã sắp xếp (chỉ có 1 cặp nghịch thế)
    vector<int> a2 = {1, 2, 4, 3, 5};
    long long d2 = insertion_sort(a2);
    in_ket_qua(a2, d2); // Dich: 1 | Mang: 1 2 3 4 5

    // Test 3: Mảng có số âm và phần tử trùng nhau
    vector<int> a3 = {4, -1, 4, 0, -5};
    long long d3 = insertion_sort(a3);
    in_ket_qua(a3, d3); // Dich: 7 | Mang: -5 -1 0 4 4

    return 0;
}

def insertion_sort(a: list[int]) -> int:
    """Sắp xếp chèn chuẩn: dùng biến key và phép dịch phải, trả về tổng số lần dịch."""
    n = len(a)
    so_lan_dich = 0
    for i in range(1, n):
        key = a[i]
        j = i - 1
        # Dịch các phần tử trong đoạn [0 .. i-1] lớn hơn key sang phải 1 vị trí
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
            so_lan_dich += 1
        a[j + 1] = key  # Đặt key vào đúng khe trống
    return so_lan_dich


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


if __name__ == "__main__":
    # Test 1: Mảng ví dụ trong bài [7, 3, 5, 2, 6]
    a1 = [7, 3, 5, 2, 6]
    d1 = insertion_sort(a1)
    in_ket_qua(a1, d1)  # Dich: 6 | Mang: 2 3 5 6 7

    # Test 2: Mảng gần như đã sắp xếp (chỉ có 1 cặp nghịch thế)
    a2 = [1, 2, 4, 3, 5]
    d2 = insertion_sort(a2)
    in_ket_qua(a2, d2)  # Dich: 1 | Mang: 1 2 3 4 5

    # Test 3: Mảng có số âm và phần tử trùng nhau
    a3 = [4, -1, 4, 0, -5]
    d3 = insertion_sort(a3)
    in_ket_qua(a3, d3)  # Dich: 7 | Mang: -5 -1 0 4 4

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

// Chèn thêm phần tử x vào mảng a đang tăng dần sao cho mảng vẫn giữ thứ tự tăng dần
// Trả về vị trí đã chèn x
int chen_giu_thu_tu(vector<int>& a, int x) {
    a.push_back(x); // Mở rộng thêm 1 ô ở cuối mảng
    int j = (int)a.size() - 2;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        --j;
    }
    a[j + 1] = x;
    return j + 1;
}

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

int main() {
    vector<int> a = {2, 5, 8, 12};

    // Chèn 6 vào giữa mảng
    int pos1 = chen_giu_thu_tu(a, 6);
    in_mang(pos1, a); // Vi tri chen: 2 | Mang: 2 5 6 8 12

    // Chèn 1 vào đầu mảng (nhỏ hơn mọi phần tử hiện có)
    int pos2 = chen_giu_thu_tu(a, 1);
    in_mang(pos2, a); // Vi tri chen: 0 | Mang: 1 2 5 6 8 12

    // Chèn 15 vào cuối mảng (lớn hơn mọi phần tử hiện có -> không cần dịch)
    int pos3 = chen_giu_thu_tu(a, 15);
    in_mang(pos3, a); // Vi tri chen: 6 | Mang: 1 2 5 6 8 12 15

    return 0;
}

def chen_giu_thu_tu(a: list[int], x: int) -> int:
    """Chèn thêm phần tử x vào danh sách a đang tăng dần, trả về vị trí đã chèn."""
    a.append(x)  # Mở rộng thêm 1 ô ở cuối danh sách
    j = len(a) - 2
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x
    return j + 1


def in_mang(vi_tri: int, a: list[int]) -> None:
    print(f"Vi tri chen: {vi_tri} | Mang: {' '.join(map(str, a))}")


if __name__ == "__main__":
    a = [2, 5, 8, 12]

    # Chèn 6 vào giữa mảng
    pos1 = chen_giu_thu_tu(a, 6)
    in_mang(pos1, a)  # Vi tri chen: 2 | Mang: 2 5 6 8 12

    # Chèn 1 vào đầu mảng (nhỏ hơn mọi phần tử hiện có)
    pos2 = chen_giu_thu_tu(a, 1)
    in_mang(pos2, a)  # Vi tri chen: 0 | Mang: 1 2 5 6 8 12

    # Chèn 15 vào cuối mảng (lớn hơn mọi phần tử hiện có -> không cần dịch)
    pos3 = chen_giu_thu_tu(a, 15)
    in_mang(pos3, a)  # Vi tri chen: 6 | Mang: 1 2 5 6 8 12 15