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

Số cặp nghịch thế (inversions) của một mảng chỉ ra: cần bao nhiêu thay đổi để chuyển mảng thành dạng đã sắp xếp. Khi mảng đã được sắp xếp, nó cần 0 nghịch thế, và trong trường hợp khác, số nghịch thế sẽ tối đa, nếu mảng được đảo ngược.

Để giải quyết bài toán này, chúng ta sẽ theo cách tiếp cận Merge sort để giảm độ phức tạp thời gian, và biến nó thành thuật toán Chia để trị (Divide and Conquer).

Input

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

Output

Số lượng nghịch thế cần thiết để sắp xếp các số theo thứ tự tăng dần.

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

Thuật toán

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

Input - Hai mảng đã được gộp, chỉ số left, right và mid.
Output - Mảng đã gộp theo thứ tự sắp xếp.

Begin
  i := left, j := mid, k := right
  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)
    done
  while left part of the array has some extra element, do
    tempArray[k] := array[i]
    increase i and k by 1
  done
  while right part of the array has some extra element, do
    tempArray[k] := array[j]
    increase j and k by 1
  done
  return count
End

mergeSort(array, tempArray, left, right)

Input - Mảng cho trước và mảng tạm, chỉ số trái và phải của mảng.
Output - Số lượng nghịch thế sau khi sắp xếp.

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

Ví dụ

#include <iostream>
using namespace std;

int merge(int arr[], int temp[], int left, int mid, int right) {
  int i, j, k;
  int count = 0;
  i = left; //i to locate first array location
  j = mid; //i to locate second array location
  k = left; //i to locate merged array location
  while ((i <= mid - 1) && (j <= right)) {
    if (arr[i] <= arr[j]){ //when left item is less than right item
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
      count += (mid - i); //find how many convertion is performed
    }
  }
  while (i <= mid - 1) //if first list has remaining item, add them in the list
    temp[k++] = arr[i++];
  while (j <= right) //if second list has remaining item, add them in the list
    temp[k++] = arr[j++];
  for (i=left; i <= right; i++)
    arr[i] = temp[i]; //store temp Array to main array
  return count;
}

int mergeSort(int arr[], int temp[], int left, int right){
  int mid, count = 0;
  if (right > left) {
    mid = (right + left)/2; //find mid index of the array
    count = mergeSort(arr, temp, left, mid); //merge sort left sub array
    count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
    count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
  }
  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);
}

Kết quả

Number of inversions are 2