C / C ++ Chương trình để đếm số nghịch đảo trong một mảng bằng cách sử dụng Merge Sort?

Các nghịch đảo của một mảng cho biết; cần bao nhiêu thay đổi để chuyển mảng thành dạng đã sắp xếp của nó. Khi một mảng đã được sắp xếp, nó cần 0 lần đảo ngược và trong trường hợp khác, số lần đảo ngược sẽ là tối đa, nếu mảng được đảo ngược.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo cách tiếp cận Sắp xếp hợp nhất để giảm độ phức tạp về thời gian và thực hiện trong thuật toán Chia và Chinh phục.

Đầu vào

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

Đầu ra

Số lần đảo ngược 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

hợp nhất (mảng, tempArray, trái, giữa, phải)

Đầu vào - Hai mảng, người đã hợp nhất, các chỉ mục bên trái, bên phải và giữa.
Đầu ra -Mảng hợp nhất 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 (mảng, tempArray, trái, phải)

Đầu vào - Cho mảng và mảng tạm thời, chỉ số bên trái và bên phải của mảng.
Đầu ra - Số lần đảo ngược 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);
}

Đầu ra

Number of inversions are 2