Inversion of Array

Task: Given an array of size N, find the inversion count of an array.

Example:

Input:

1

5

2 4 1 3 5

Output:

3

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. long long int c;
5. void count(long long int *arr,int l,int m,int r)
6. {
7.      int n1=m-l+1;
8.      int n2=r-m;
9.      long long int a[n1],b[n2];
10.      for(int i=0;i<n1;i++)
11.      {
12.          a[i]=arr[l+i];
13.      }
14.      for(int j=0;j<n2;j++)
15.      {
16.          b[j]=arr[m+1+j];
17.      }
18.      int i=0,j=0,k=l;
19.      while(i<n1&&j<n2)
20.      {
21.          if(a[i]<=b[j])
22.          {
23.              arr[k]=a[i];
24.              i++;
25.          }
26.          else
27.          {
28.              arr[k]=b[j];
29.              j++;
30.              c+=n1-i;
31.          }
32.          k++;
33.      }
34.      while(i<n1)
35.      {
36.          arr[k]=a[i];
37.          k++,i++;
38.      }
39.      while(j<n2)
40.      {
41.          arr[k]=b[j];
42.          k++,j++;
43.      }
44. }
45. void inversionOfArray(long long int *a,int i,int j)
46. {
47.     if(i==j)
48.     {
49.         return ;
50.     }
51.     else
52.     {
53.         int m=floor((i+j)/2);
54.         inversionOfArray(a,i,m);
55.         inversionOfArray(a,m+1,j);
56.         count(a,i,m,j);
57.     }
58. }
59. int main()
60.  {
61. int t;
62. cin>>t;
63. while(t--)
64. {
65.     int n;
66.     cin>>n;
67.     long long int a[n];
68.     for(int i=0;i<n;i++)
69.     {
70.         cin>>a[i];
71.     }
72.     c=0;
73.     inversionOfArray(a,0,n-1);
74.     cout<<c<<endl;
75. }
76. return 0;
77. }

---

Here is the Video:

---