โปรแกรม C/C++ นับ Inversions ใน Array ด้วย Merge Sort

Inversion Count คือ จำนวนคู่ (i, j) ที่ i < j แต่ A[i] > A[j] ปัญหา Classical แก้ด้วย Merge Sort นับขณะ Merge

ภาพประกอบกระบวนการ Merge และนับ Inversion

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

คำอธิบาย

Inversion Count ของ Array: นับคู่ (i,j) ที่ iA[j] ตัวอย่าง 5 คู่: (9,6), (9,4), (9,5), (6,4), (6,5)

1. เปรียบเทียบค่าขององค์ประกอบ 2. เพิ่ม Counter หาก Index น้อยกว่ามีค่ามากกว่า 3. แสดงผล

ตัวอย่าง

#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;
}