Đếm số đường chéo (cross lines) khi sắp xếp mảng bằng Insertion Sort C++

Cho mảng các phần tử phân biệt chưa sắp xếp. "Đường chéo" (cross lines) được định nghĩa là số lần một phần tử phải "vượt qua" các phần tử khác khi đưa vào vị trí đúng trong Insertion Sort. Tức là số cặp nghịch thế (inversions) của mảng.

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {4, 3, 1, 2}
• Output: 5
• Giải thích: Các cặp nghịch thế: (4,3), (4,1), (4,2), (3,1), (3,2) = 5 cặp.

Ví dụ 2:

• Input: arr = {0, 1, 5, 3}
• Output: 1
• Giải thích: Chỉ cặp (5,3).

Mã nguồn C++ (Insertion Sort đếm shift)

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

int insertionSort(int arr[], int n) {
    int count = 0;
    for (int i = 1; i < n; i++) {
        int item = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > item) {
            arr[j + 1] = arr[j];
            j--;
            count++; // Mỗi lần dịch = 1 cross line
        }
        arr[j + 1] = item;
    }
    return count;
}

int main() {
    int arr[] = {4, 5, 3, 1, 2};
    int n = 5;
    cout << "So duong cheo (nghich the): " << insertionSort(arr, n);
    return 0;
}

Kết quả chạy chương trình

So duong cheo (nghich the): 8

Tối ưu hóa O(n log n) - Merge Sort đếm nghịch thế

Insertion Sort O(n²) quá chậm cho n lớn. Dùng Merge Sort biến đổi để đếm inversions:

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

long long mergeAndCount(vector& arr, int l, int m, int r) {
    vector left(arr.begin() + l, arr.begin() + m + 1);
    vector right(arr.begin() + m + 1, arr.begin() + r + 1);
    
    long long count = 0;
    int i = 0, j = 0, k = l;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else {
            arr[k++] = right[j++];
            count += left.size() - i; // Tất cả phần tử còn lại trong left > right[j]
        }
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
    return count;
}

long long mergeSortAndCount(vector& arr, int l, int r) {
    if (l >= r) return 0;
    int m = l + (r - l) / 2;
    long long count = mergeSortAndCount(arr, l, m);
    count += mergeSortAndCount(arr, m + 1, r);
    count += mergeAndCount(arr, l, m, r);
    return count;
}

long long countCrossLines(vector arr) {
    return mergeSortAndCount(arr, 0, arr.size() - 1);
}

Độ phức tạp

Lưu ý

• "Cross lines" chính là khái niệm inversions (cặp nghịch thế) trong thuật toán sắp xếp.
• Insertion Sort đếm chính xác số lần shift = số inversions.
• Với n ≤ 10⁵, bắt buộc dùng O(n log n).