Advertisement
kartikkukreja

Counting inversions with merge sort

May 18th, 2013
306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. /*
  5.  * Merges the two sorted subarrays A[low...mid] and A[mid+1...high]
  6.  * and counts the number of split inversions
  7.  */
  8. int mergeAndCountSplitInv(int *A, int *helper, int low, int mid, int high)  {
  9.     // Copy both parts into the helper array
  10.     memcpy(helper + low, A + low, (high - low + 1)*sizeof(int));
  11.  
  12.     int i = low, j = mid + 1, k = low, split = 0;
  13.     // Copy the smallest values from either the left or the right side back
  14.     // to the original array
  15.     while (i <= mid && j <= high) {
  16.         if(helper[i] <= helper[j])
  17.             A[k] = helper[i++];
  18.         else {
  19.             A[k] = helper[j++];
  20.             split += mid + 1 - i;
  21.         }
  22.         k++;
  23.     }
  24.     // Copy the rest of the left side of the array into the target array
  25.     while (i <= mid)
  26.         A[k++] = helper[i++];
  27.  
  28.     return split;
  29. }
  30.  
  31. int auxCountInversion(int *A, int *helper, int low, int high)   {
  32.     if(low < high)  {
  33.         int mid = (low + high)/2;
  34.         int left = auxCountInversion(A, helper, low, mid);
  35.         int right = auxCountInversion(A, helper, mid+1, high);
  36.         int split = mergeAndCountSplitInv(A, helper, low, mid, high);
  37.         return left + right + split;
  38.     }
  39.     return 0;
  40. }
  41.  
  42. int countInversion(int *A, int N)   {
  43.     int *helper = new int[N];
  44.     return auxCountInversion(A, helper, 0, N - 1);
  45. }
  46.  
  47. int main()  {
  48.     int *A, N, i;
  49.  
  50.     printf("Enter size of array : ");
  51.     scanf("%d", &N);
  52.     A = new int[N];
  53.     printf("Enter %d integers :\n", N);
  54.     for(i=0; i<N; i++)
  55.         scanf("%d", &A[i]);
  56.  
  57.     printf("No. of inversions : %d\n", countInversion(A, N));
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement