C/C++ program written using the merge sort algorithm to calculate reverse numbers in an array

The reversed representation of an array; how many changes are required to convert the array into its sorted form. When the array is already sorted, 0 reversals are required, while in other cases, if the array is reversed, the maximum number of reversals will be achieved.

In order to solve this problem, we will follow the merge sort method to reduce the time complexity and use the divide and conquer algorithm.

Input

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

Output

The number of reversals required to sort the numbers in ascending order.

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

Algorithm

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

Input - Two arrays, who have been merged, left, Right and middle index.

Output - Arrays merged in sorted order.

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 - Given an array and a temporary array, the left and right indices of the array.

Output -The number of reverse-ordered pairs after sorting.

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

Example

Real-time demonstration

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

Output

Number of inversions are 2

The above is the detailed content of C/C++ program written using the merge sort algorithm to calculate reverse numbers in an array. For more information, please follow other related articles on the PHP Chinese website!