### dash_______'s blog

By dash_______, 3 years ago,

### INVERSION COUNT IN AN ARRAY

Given an array arr of size n we have to find the inversion count in the array.

what is inversion count :- sum of inversion count of all indexes.

inversion count of index i = number of index j such that j>i and arr[i]>arr[j]

or number of indexes with value lesser the arr[i] in the right of index i.

OR

number of index j such that j<i and arr[j]>arr[i] or number of indexes with value greater the arr[i] in the left of index i.

Example

              0   1   2   3   4
int arr[] = { 1 , 5 , 2 , 4 , 3 }

for index 0 :- 0
for index 1 :- 3 ( index '2','3','4')
for index 2 :- 0
for index 3 :- 1 ( index '4')
for index 4 :- 0

so the inversion count of above array is equal to 0 + 3 + 0 + 1 + 0 = 4



#### BRUTE FORCE METHOD

Brute method use two loops.

1. Outer loop traverse the whole array.

2. Inner loop count the inversion count for particular index i.

CODE

int Inversion_Count(int arr[],int n){
int inversion_count=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(arr[i]>arr[j]){
inversion_count+=1;
}
}
}
}



TIME COMPLEXITY :- O(N^2) SPACE COMPLEXITY :- O(1)

#### USING MERGE SORT

basic merge sort algorithm

step 1 :- divide the array in two equal parts

step 2 :- sort the two equal parts

step 3 :- merge two sorted parts

**for sorting two equal parts we again use merge sort**



more on merge sort

Now, how merge sort can be used to find inversion count.

while merging two sorted array

if left[i]<=right[j] continue

if left[i]>right[j] then this right[j] is smaller than all the next upcoming elements in left so, for every next element in left right[j] is smaller so inversion count should be increased by (size of left array)-i.

CODE

int inversion_count=0;

int merge(int arr[],int l,int mid,int r){
int* temp = new int[r-l+1];
int i=l,j=mid+1;
int t=0;
while(i<=mid && j<=r){
if(arr[i]<=arr[j]){
temp[t++]=arr[i++];
}
else{
temp[t++]=arr[j++];
inversion_count+=(mid-i+1);
}
}
while(i<=mid){
temp[t++]=arr[i++];
}
while(j<=r){
temp[t++]=arr[j++];
}
t=0;
for(int i=l;i<=r;i++){
arr[i]=temp[t++];
}
delete [] temp;
}

int merge_sort(int arr[],int l,int r){

if(l>=r){
return 0;
}

int mid=(l+r)/2;

merge_sort(arr,l,mid);      //recursive calls to sort left part
merge_sort(arr,mid+1,r);    //recursive calls to sort right part

merge(arr,l,mid,r);

}



TIME COMPLEXITY :- O(NlogN) SPACE COMPLEXITY :- O(N)

#### USING BINARY INDEXED TREE/FENWICK TREE

for finding inversion count for index i in the given array. we can find number of index j such that j<i and arr[j]>arr[i]. BIT uses the fact that a number can be broken into several powers of 2.

In BIT index i stores the sum or product or anything of previous m elements of array. where
m is 2^LSB of i.

like this

BASIC BIT CODE

const int N=1e6;
int BIT[N];

// indexing in BST starts from 1

int i=idx;
while(i<N){
BIT[i]+=val;
i+=(i&(-i));
}
}

int query(int idx){           // returns sum of values from range 1 to idx
int sum=0;
while(idx>0){
sum+=BIT[idx];
idx+=(idx&(-idx));
}
return sum;
}



more on BIT

we can take array elements as indexes for BIT array such that BIT array store count of value arr[i].

while traversing given array arr we keep on increasing count of arr[i] in the bit array and

calculating number of indexes with value greater than arr[i] or (i — number of index with

value less than equal to arr[i]).

number of index with value less than equal to arr[i] = query(arr[i]).

CODE

const int N=1e6;
int BIT[N];

// indexing in BST starts from 1

while(idx<N){
BIT[idx]+=val;
idx+=(idx&(-idx));
}
}

int query(int idx){           // returns sum of values from range 1 to idx
int sum=0;
while(idx>0){
sum+=BIT[idx];
idx-=(idx&(-idx));
}
return sum;
}

int inversion_count(int arr[],int n){
int icount=0;
for(int i=1;i<=n;i++){
add(arr[i],1);         // increases the count of arr[i] by 1
int a=query(arr[i]);   // a stores number of indexes with value less than and equal to arr[i]

icount+=(i-a);
}
return icount;
}



TIME COMPLEXITY :- O(NlogN) SPACE COMPLEXITY :- O(N)

note :- since we used array elements as indexes so we cannot use this method if values in array are greater than 1e9 because we cannot create an array of such a bigger size in C++ and if array contains 0 as element then also we cannot use this method.

• -45

| Write comment?