Sắp xếp nổi bọt (Bubble Sort): giải thích từng bước, tối ưu dừng sớm và code C++, Python

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

// Bản cơ bản: luôn chạy đủ n - 1 lượt ngoài
void bubble_sort_co_ban(vector<int>& a) {
    int n = (int)a.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}

// Bản tối ưu: dùng cờ swapped để dừng ngay khi mảng đã có thứ tự
// Trả về số lượt ngoài thực tế đã chạy
int bubble_sort_toi_uu(vector<int>& a) {
    int n = (int)a.size();
    int so_luot = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        ++so_luot;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) {
            break; // Không có cặp nào nghịch thế -> mảng đã tăng dần
        }
    }
    return so_luot;
}

void in_mang(const vector<int>& a, int so_luot) {
    cout << "So luot: " << so_luot << " | 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 [5, 1, 4, 2, 8]
    vector<int> a1 = {5, 1, 4, 2, 8};
    int luot1 = bubble_sort_toi_uu(a1);
    in_mang(a1, luot1); // So luot: 3 | Mang: 1 2 4 5 8

    // Test 2: Mảng đã tăng dần sẵn -> dừng ngay sau 1 lượt kiểm tra
    vector<int> a2 = {10, 20, 30, 40, 50};
    int luot2 = bubble_sort_toi_uu(a2);
    in_mang(a2, luot2); // So luot: 1 | Mang: 10 20 30 40 50

    // Test 3: Mảng giảm dần có phần tử âm và trùng nhau
    vector<int> a3 = {9, 4, 4, -2, -5};
    int luot3 = bubble_sort_toi_uu(a3);
    in_mang(a3, luot3); // So luot: 4 | Mang: -5 -2 4 4 9

    return 0;
}

def bubble_sort_co_ban(a: list[int]) -> None:
    """Bản cơ bản: luôn chạy đủ n - 1 lượt ngoài."""
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]


def bubble_sort_toi_uu(a: list[int]) -> int:
    """Bản tối ưu: dùng cờ swapped dừng sớm, trả về số lượt ngoài đã chạy."""
    n = len(a)
    so_luot = 0
    for i in range(n - 1):
        swapped = False
        so_luot += 1
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break  # Không có cặp nào nghịch thế -> mảng đã tăng dần
    return so_luot


def in_mang(a: list[int], so_luot: int) -> None:
    print(f"So luot: {so_luot} | Mang: {' '.join(map(str, a))}")


if __name__ == "__main__":
    # Test 1: Mảng ví dụ trong bài [5, 1, 4, 2, 8]
    a1 = [5, 1, 4, 2, 8]
    luot1 = bubble_sort_toi_uu(a1)
    in_mang(a1, luot1)  # So luot: 3 | Mang: 1 2 4 5 8

    # Test 2: Mảng đã tăng dần sẵn -> dừng ngay sau 1 lượt kiểm tra
    a2 = [10, 20, 30, 40, 50]
    luot2 = bubble_sort_toi_uu(a2)
    in_mang(a2, luot2)  # So luot: 1 | Mang: 10 20 30 40 50

    # Test 3: Mảng giảm dần có phần tử âm và trùng nhau
    a3 = [9, 4, 4, -2, -5]
    luot3 = bubble_sort_toi_uu(a3)
    in_mang(a3, luot3)  # So luot: 4 | Mang: -5 -2 4 4 9

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

// Đếm tổng số lần hoán đổi khi chạy Bubble Sort
long long dem_hoan_doi_bubble(vector<int> a) {
    int n = (int)a.size();
    long long so_lan_doi = 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]);
                ++so_lan_doi;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return so_lan_doi;
}

// Đếm trực tiếp số cặp nghịch thế (u < v nhưng a[u] > a[v])
long long dem_cap_nghich_the(const vector<int>& a) {
    int n = (int)a.size();
    long long nghich_the = 0;
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            if (a[u] > a[v]) {
                ++nghich_the;
            }
        }
    }
    return nghich_the;
}

int main() {
    vector<vector<int>> cac_mang = {
        {5, 1, 4, 2, 8},       // 4 cặp: (5,1), (5,4), (5,2), (4,2)
        {4, 3, 2, 1},          // Mảng giảm dần 4 phần tử: 4*3/2 = 6 cặp
        {1, 2, 2, 5, 9}        // Đã tăng dần: 0 cặp
    };

    for (const auto& a : cac_mang) {
        cout << "Swaps: " << dem_hoan_doi_bubble(a)
             << " | Inversions: " << dem_cap_nghich_the(a) << "\n";
    }
    return 0;
}

def dem_hoan_doi_bubble(mang_goc: list[int]) -> int:
    """Đếm tổng số lần hoán đổi khi chạy Bubble Sort."""
    a = mang_goc[:]
    n = len(a)
    so_lan_doi = 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]
                so_lan_doi += 1
                swapped = True
        if not swapped:
            break
    return so_lan_doi


def dem_cap_nghich_the(a: list[int]) -> int:
    """Đếm trực tiếp số cặp nghịch thế (u < v nhưng a[u] > a[v])."""
    n = len(a)
    nghich_the = 0
    for u in range(n):
        for v in range(u + 1, n):
            if a[u] > a[v]:
                nghich_the += 1
    return nghich_the


if __name__ == "__main__":
    cac_mang = [
        [5, 1, 4, 2, 8],   # 4 cặp: (5,1), (5,4), (5,2), (4,2)
        [4, 3, 2, 1],      # Mảng giảm dần 4 phần tử: 4*3/2 = 6 cặp
        [1, 2, 2, 5, 9],   # Đã tăng dần: 0 cặp
    ]

    for a in cac_mang:
        print(f"Swaps: {dem_hoan_doi_bubble(a)} | Inversions: {dem_cap_nghich_the(a)}")