C/C++ program written using merge sort algorithm to calculate reverse logarithm in an array?

The reversal count that occurs when sorting a given array is called reversal counting. The inverse problem is a classic problem that can be solved using the merge sort algorithm. In this problem v we will count all elements to its left that are greater than it and add the count to the output. This logic is completed in the merge function of merge sort.

To understand this topic better, let us take an example. Let us consider the two sub-arrays involved in the merge process -

##

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

#include  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) // if run size == 1 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; }

Copy after login

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