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

Inversions ของอาร์เรย์บอกว่าต้องสลับกี่ครั้งถึงจะเรียงลำดับได้ ถ้าเรียงแล้ว inversion = 0 ถ้าเรียงย้อนกลับ inversion สูงสุด

ใช้แนวคิด Merge Sort เพื่อลดความซับซ้อนเวลา ใช้ Divide and Conquer

Input

A sequence of numbers. (1, 5, 6, 4, 20)

Output

จำนวน inversions ที่ต้องการเพื่อจัดเรียงข้อมูลจากน้อยไปมาก

Here the number of inversions are 2.
First inversion: (1, 5, 4, 6, 20)
Second inversion: (1, 4, 5, 6, 20)

อัลกอริทึม

merge(array, tempArray, left, mid, right)

Begin
    i := left, j := mid, k := left
    count := 0
    while i <= mid-1 and j <= right, do
        if array[i] <= array[j], then
            tempArray[k] := array[i]
            increase i and k by 1
        else
            tempArray[k] := array[j]
            increase j and k by 1
            count := count + (mid - i)
        end if
    done
    while left part has extra elements, do
        tempArray[k] := array[i]; increase i, k
    done
    while right part has extra elements, do
        tempArray[k] := array[j]; increase j, k
    done
    copy tempArray to array
    return count
End

mergeSort(array, tempArray, left, right)

Begin
    count := 0
    if right > left, then
        mid := (right + left)/2
        count := mergeSort(array, tempArray, left, mid)
        count := count + mergeSort(array, tempArray, mid+1, right)
        count := count + merge(array, tempArray, left, mid+1, right)
    return count
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid, k = left;
    int count = 0;
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            count += (mid - i);
        }
    }
    while (i <= mid - 1) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = temp[i];
    return count;
}

int mergeSort(int arr[], int temp[], int left, int right) {
    int mid, count = 0;
    if (right > left) {
        mid = (right + left) / 2;
        count = mergeSort(arr, temp, left, mid);
        count += mergeSort(arr, temp, mid+1, right);
        count += merge(arr, temp, left, mid+1, right);
    }
    return count;
}

int arrInversion(int arr[], int n) {
    int temp[n];
    return mergeSort(arr, temp, 0, n - 1);
}

int main() {
    int arr[] = {1, 5, 6, 4, 20};
    int n = 5;
    cout << "Number of inversions are " << arrInversion(arr, n);
}

ผลลัพธ์

Number of inversions are 2