Chương trình C/C++ đếm nghịch thế trong mảng dùng Merge Sort

Số nghịch thế (inversion count) là số cặp (i,j) với i<j và A[i]>A[j]. Giải bằng Merge Sort: trong hàm merge, khi lấy phần tử từ mảng phải trước mảng trái, tăng đếm thêm (mid - i + 1).

Ví dụ mảng {1,9,6,4,5} có 5 nghịch thế: (9,6), (9,4), (9,5), (6,4), (6,5).

Input: arr[] = { 1, 9, 6, 4, 5} Output: Inversion count is 5

Ví dụ

#include <stdio.h>

int Merge(int arr[], int aux[], int low, int mid, int high) {
    int k = low, i = low, j = mid + 1;
    int inversionCount = 0;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            aux[k++] = arr[i++];
        } else {
            aux[k++] = arr[j++];
            inversionCount += (mid - i + 1); // NOTE
        }
    }
    while (i <= mid) aux[k++] = arr[i++];
    for (int i = low; i <= high; i++) arr[i] = aux[i];
    return inversionCount;
}

int MergeSort(int arr[], int aux[], int low, int high) {
    if (high == low) return 0;
    int mid = (low + ((high - low) >> 1));
    int inversionCount = 0;
    inversionCount += MergeSort(arr, aux, low, mid);
    inversionCount += MergeSort(arr, aux, mid + 1, high);
    inversionCount += Merge(arr, aux, low, mid, high);
    return inversionCount;
}

int main() {
    int arr[] = { 1, 9, 6, 4, 5 };
    int N = 5;
    int aux[N];
    for (int i = 0; i < N; i++) aux[i] = arr[i];
    printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
    return 0;
}