Bài 26.4: Bài toán đếm số đảo trong C++

Chào mừng các bạn quay trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng nhau khám phá một bài toán kinh điển trong lĩnh vực giải thuật: Bài toán đếm số đảo (Counting Inversions). Nghe có vẻ đơn giản, nhưng nó lại ẩn chứa nhiều điều thú vị và là cánh cửa dẫn đến những kỹ thuật giải thuật mạnh mẽ hơn!

Số Đảo Là Gì?

Đầu tiên, chúng ta cần hiểu rõ "số đảo" là gì trong ngữ cảnh của một mảng hay dãy số.

Cho một mảng arr gồm n phần tử. Một số đảo (hay cặp nghịch thế) là một cặp chỉ số (i, j) sao cho i < j và arr[i] > arr[j]. Nói cách khác, đó là một cặp phần tử đứng sai vị trí so với thứ tự được sắp xếp tăng dần.

Ví dụ:

Mảng [8, 4, 2, 1]
- Các cặp chỉ số (i, j) với i < j: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3)
- Kiểm tra điều kiện arr[i] > arr[j]:
  - (0,1): arr[0]=8, arr[1]=4. 8 > 4. Đây là 1 số đảo.
  - (0,2): arr[0]=8, arr[2]=2. 8 > 2. Đây là 1 số đảo.
  - (0,3): arr[0]=8, arr[3]=1. 8 > 1. Đây là 1 số đảo.
  - (1,2): arr[1]=4, arr[2]=2. 4 > 2. Đây là 1 số đảo.
  - (1,3): arr[1]=4, arr[3]=1. 4 > 1. Đây là 1 số đảo.
  - (2,3): arr[2]=2, arr[3]=1. 2 > 1. Đây là 1 số đảo.
- Tổng cộng có 6 số đảo.
Mảng [1, 2, 3, 4]
- Không có cặp (i, j) nào với i < j mà arr[i] > arr[j].
- Tổng cộng có 0 số đảo. Mảng đã được sắp xếp hoàn toàn.
Mảng [4, 3, 2, 1]
- Tất cả các cặp (i, j) với i < j đều thỏa mãn arr[i] > arr[j].
- Số lượng số đảo chính là số lượng các cặp (i, j) với i < j trong mảng có độ dài n, công thức là n*(n-1)/2. Với n=4, ta có 4*3/2 = 6 số đảo. Mảng này được sắp xếp ngược hoàn toàn.

Số lượng số đảo trong một mảng là một chỉ số cho thấy mức độ "lộn xộn" hay "không được sắp xếp" của mảng đó. Mảng càng có nhiều số đảo, nó càng xa trạng thái được sắp xếp tăng dần.

Bài toán đặt ra là: Đếm tổng số lượng các cặp số đảo trong một mảng cho trước.

Tại sao bài toán này lại quan trọng?

Tuy nghe có vẻ lý thuyết, bài toán đếm số đảo có ứng dụng trong thực tế, ví dụ:

Đo lường sự tương đồng giữa hai danh sách xếp hạng.
Trong phân tích dữ liệu, nó có thể được dùng để đánh giá mức độ ngẫu nhiên hoặc trật tự của dữ liệu.
Nó là một bài toán kinh điển thường xuất hiện trong các cuộc phỏng vấn về giải thuật, giúp đánh giá khả năng tư duy giải quyết vấn đề bằng các kỹ thuật như chia để trị.

Bây giờ, chúng ta hãy xem các cách để giải quyết bài toán này trong C++.

Cách 1: Thuật toán "Vét cạn" (Brute Force)

Đây là cách làm đơn giản và trực tiếp nhất, dựa đúng theo định nghĩa của số đảo. Chúng ta sẽ duyệt qua tất cả các cặp chỉ số (i, j) mà i < j và kiểm tra xem arr[i] > arr[j] có đúng không. Nếu đúng, ta tăng bộ đếm lên.

#include <iostream>
#include <vector>
#include <string>

// Hàm đếm số đảo bằng thuật toán vét cạn
int demDao_vetCan(const vector<int>& a) {
    int dem = 0;
    int m = a.size();

    for (int i = 0; i < m - 1; ++i) {
        for (int j = i + 1; j < m; ++j) {
            if (a[i] > a[j]) {
                dem++;
            }
        }
    }
    return dem;
}

// Hàm trợ giúp để in mảng
string inMang(const vector<int>& a) {
    string chuoi = "[";
    for (size_t k = 0; k < a.size(); ++k) {
        chuoi += to_string(a[k]);
        if (k < a.size() - 1) {
            chuoi += ", ";
        }
    }
    chuoi += "]";
    return chuoi;
}

int main() {
    vector<int> a1 = {8, 4, 2, 1};
    vector<int> a2 = {1, 20, 6, 4, 5};
    vector<int> a3 = {1, 2, 3, 4};
    vector<int> a4 = {4, 3, 2, 1};

    cout << "Mang " << inMang(a1) << " co "
              << demDao_vetCan(a1) << " so dao (vet can).\n";
    cout << "Mang " << inMang(a2) << " co "
              << demDao_vetCan(a2) << " so dao (vet can).\n";
    cout << "Mang " << inMang(a3) << " co "
              << demDao_vetCan(a3) << " so dao (vet can).\n";
    cout << "Mang " << inMang(a4) << " co "
              << demDao_vetCan(a4) << " so dao (vet can).\n";

    return 0;
}

Output:

Mang [8, 4, 2, 1] co 6 so dao (vet can).
Mang [1, 20, 6, 4, 5] co 5 so dao (vet can).
Mang [1, 2, 3, 4] co 0 so dao (vet can).
Mang [4, 3, 2, 1] co 6 so dao (vet can).

Giải thích Code:

Hàm demDao_vetCan nhận vào một vector a.
Chúng ta dùng hai vòng lặp lồng nhau. Vòng lặp ngoài với biến i đi từ 0 đến m-2. Vòng lặp trong với biến j đi từ i+1 đến m-1. Điều này đảm bảo chúng ta chỉ xem xét các cặp (i, j) mà i < j.
Bên trong vòng lặp trong cùng, chúng ta so sánh a[i] và a[j]. Nếu a[i] > a[j], chúng ta tìm thấy một số đảo và tăng biến dem.
Sau khi duyệt hết tất cả các cặp, hàm trả về tổng dem.
Hàm main chỉ đơn giản là tạo ra các mảng ví dụ và gọi hàm đếm. Hàm inMang giúp in mảng ra màn hình một cách dễ đọc hơn.

Đánh giá thuật toán:

Thuật toán này dễ hiểu và dễ cài đặt. Tuy nhiên, nó có một nhược điểm lớn: độ phức tạp thời gian là O(n^2). Điều này có nghĩa là nếu kích thước mảng n tăng gấp đôi, thời gian chạy sẽ tăng gấp bốn lần. Với các mảng có kích thước lớn (ví dụ, hàng chục nghìn hoặc hàng trăm nghìn phần tử), thuật toán này sẽ rất chậm và có thể không khả thi.

Chúng ta cần một cách hiệu quả hơn!

Cách 2: Thuật toán "Chia để trị" dựa trên Merge Sort

Đây là cách giải quyết bài toán đếm số đảo một cách hiệu quả hơn nhiều, thường được sử dụng. Ý tưởng chính là áp dụng kỹ thuật chia để trị (divide and conquer), tương tự như thuật toán Merge Sort.

Nhắc lại một chút về Merge Sort:

Chia: Chia mảng làm đôi.
Trị: Đệ quy sắp xếp hai nửa mảng con.
Trộn (Merge): Trộn hai nửa mảng con đã được sắp xếp lại thành một mảng đã sắp xếp hoàn chỉnh.

Điểm mấu chốt ở đây là chúng ta có thể đếm số đảo trong bước trộn (merge). Khi trộn hai nửa mảng đã được sắp xếp, ta có thể đếm được số đảo mà một phần tử nằm ở nửa bên trái, còn phần tử còn lại nằm ở nửa bên phải.

Hãy xem xét hai nửa mảng đã được sắp xếp: left_half và right_half. Khi ta đang trộn chúng lại thành một mảng kết quả, ta dùng hai con trỏ (hoặc chỉ số), một cho left_half (gọi là i) và một cho right_half (gọi là j).

Nếu left_half[i] <= right_half[j]: Phần tử từ nửa trái nhỏ hơn hoặc bằng, nó không tạo ra số đảo với right_half[j] hoặc bất kỳ phần tử nào sau right_half[j] (vì right_half đã sắp xếp). Ta chỉ việc đưa left_half[i] vào mảng kết quả và tiến con trỏ i lên.
Nếu left_half[i] > right_half[j]: Đây là lúc chúng ta tìm thấy số đảo! Phần tử left_half[i] lớn hơn right_half[j]. Quan trọng hơn, vì left_half đã được sắp xếp, tất cả các phần tử còn lại trong left_half từ vị trí i trở đi (left_half[i], left_half[i+1], ..., left_half[mid]) đều lớn hơn hoặc bằng left_half[i], và do đó, chúng đều lớn hơn right_half[j]. Mỗi phần tử trong số này tạo thành một số đảo với right_half[j]. Số lượng các phần tử còn lại này chính là (mid - i + 1) (với mid là chỉ số cuối cùng của nửa trái). Ta cộng số này vào tổng số đảo. Sau đó, ta đưa right_half[j] vào mảng kết quả và tiến con trỏ j lên.

Bằng cách này, trong khi trộn hai nửa đã sắp xếp (một bước mất thời gian O(n)), chúng ta đã đếm được tất cả các số đảo vắt ngang qua ranh giới giữa hai nửa đó. Tổng số đảo của toàn mảng sẽ là tổng số đảo trong nửa trái (đệ quy), cộng với tổng số đảo trong nửa phải (đệ quy), cộng với số đảo vắt ngang qua ranh giới (đếm trong lúc trộn).

Đây là cài đặt C++ cho thuật toán này:

#include <iostream>
#include <vector>
#include <string>

long long tronVaDem(vector<int>& a, int l, int giua, int r) {
    vector<int> tam;
    int i = l;
    int j = giua + 1;
    long long demDao = 0;

    while (i <= giua && j <= r) {
        if (a[i] <= a[j]) {
            tam.push_back(a[i]);
            i++;
        } else {
            tam.push_back(a[j]);
            j++;
            demDao += (long long)(giua - i + 1);
        }
    }

    while (i <= giua) {
        tam.push_back(a[i]);
        i++;
    }

    while (j <= r) {
        tam.push_back(a[j]);
        j++;
    }

    for (int k = 0; k < tam.size(); ++k) {
        a[l + k] = tam[k];
    }

    return demDao;
}

long long sapXepTronVaDem(vector<int>& a, int l, int r) {
    long long demDao = 0;
    if (l < r) {
        int giua = l + (r - l) / 2;

        demDao += sapXepTronVaDem(a, l, giua);
        demDao += sapXepTronVaDem(a, giua + 1, r);
        demDao += tronVaDem(a, l, giua, r);
    }
    return demDao;
}

// Hàm trợ giúp để in mảng (cho dễ nhìn ví dụ)
string inMang(const vector<int>& a) {
    string chuoi = "[";
    for (size_t k = 0; k < a.size(); ++k) {
        chuoi += to_string(a[k]);
        if (k < a.size() - 1) {
            chuoi += ", ";
        }
    }
    chuoi += "]";
    return chuoi;
}

int main() {
    vector<int> a1 = {8, 4, 2, 1};
    vector<int> a2 = {1, 20, 6, 4, 5};
    vector<int> a3 = {1, 2, 3, 4};
    vector<int> a4 = {4, 3, 2, 1};

    vector<int> a1_b = a1;
    vector<int> a2_b = a2;
    vector<int> a3_b = a3;
    vector<int> a4_b = a4;

    cout << "Mang " << inMang(a1) << " co "
              << sapXepTronVaDem(a1_b, 0, a1_b.size() - 1) << " so dao (Merge Sort).\n";
    cout << "Mang " << inMang(a2) << " co "
              << sapXepTronVaDem(a2_b, 0, a2_b.size() - 1) << " so dao (Merge Sort).\n";
    cout << "Mang " << inMang(a3) << " co "
              << sapXepTronVaDem(a3_b, 0, a3_b.size() - 1) << " so dao (Merge Sort).\n";
    cout << "Mang " << inMang(a4) << " co "
              << sapXepTronVaDem(a4_b, 0, a4_b.size() - 1) << " so dao (Merge Sort).\n";

    return 0;
}

Output:

Mang [8, 4, 2, 1] co 6 so dao (Merge Sort).
Mang [1, 20, 6, 4, 5] co 5 so dao (Merge Sort).
Mang [1, 2, 3, 4] co 0 so dao (Merge Sort).
Mang [4, 3, 2, 1] co 6 so dao (Merge Sort).

Giải thích Code:

Hàm sapXepTronVaDem là hàm đệ quy chính. Nó nhận mảng a và phạm vi l, r cần xử lý.
Điều kiện dừng đệ quy là l < r. Nếu l >= r, đoạn mảng chỉ có 0 hoặc 1 phần tử, không có số đảo nào, nên ta trả về 0.
Tìm điểm giữa giua và gọi đệ quy cho hai nửa [l...giua] và [giua+1...r]. Kết quả trả về từ các lời gọi đệ quy này chính là tổng số đảo bên trong mỗi nửa.
Sau khi hai nửa con đã được xử lý (và sắp xếp bởi quá trình đệ quy), chúng ta gọi hàm tronVaDem để trộn hai nửa a[l...giua] và a[giua+1...r] lại với nhau và đếm số đảo vắt ngang qua giua.
Kết quả cuối cùng là tổng của số đảo ở nửa trái, nửa phải và số đảo vắt ngang.
Hàm tronVaDem thực hiện việc trộn giống hệt như bước trộn trong Merge Sort thông thường, nhưng với một bổ sung quan trọng: khi một phần tử từ nửa phải (a[j]) được chọn trước một phần tử từ nửa trái (a[i]), điều đó có nghĩa là a[i] > a[j]. Tại thời điểm này, a[j] sẽ tạo thành số đảo với a[i] và tất cả các phần tử còn lại trong nửa trái (vì nửa trái đã được sắp xếp tăng dần). Số lượng các phần tử còn lại này là (giua - i + 1). Chúng ta cộng giá trị này vào demDao.
Lưu ý rằng thuật toán này sắp xếp mảng đầu vào như một tác dụng phụ. Nếu bạn muốn giữ nguyên mảng gốc, bạn cần truyền một bản sao vào hàm sapXepTronVaDem.
Sử dụng long long cho biến đếm demDao để tránh tràn số khi làm việc với mảng lớn.

Đánh giá thuật toán:

Thuật toán này có độ phức tạp thời gian là O(n log n). Điều này xuất phát từ cấu trúc đệ quy tương tự Merge Sort. Bước chia mất O(1), bước đệ quy gọi 2 lần trên mảng kích thước n/2, và bước trộn (cùng với đếm) mất O(n). Công thức đệ quy T(n) = 2T(n/2) + O(n) có nghiệm là O(n log n).

So với O(n^2), O(n log n) là một sự cải thiện đáng kể, đặc biệt với n lớn. Ví dụ:

n = 1000: O(n^2) = 1,000,000; O(n log n) ≈ 1000 log₂(1000) ≈ 1000 10 = 10,000.
n = 100,000: O(n^2) = 10,000,000,000; O(n log n) ≈ 100,000 log₂(100,000) ≈ 100,000 17 ≈ 1,700,000.

Sự khác biệt là rất lớn!

Độ phức tạp không gian: Thuật toán Merge Sort yêu cầu không gian phụ trợ để lưu trữ mảng tạm trong lúc trộn. Kích thước của mảng tạm này có thể lên tới O(n) ở mỗi cấp đệ quy, nhưng tổng không gian cần thiết là O(n).

Comments

There are no comments at the moment.