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

void add(int idx,int val){     // val is added to index a
    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

void add(int idx,int val){     // val is added to index a
    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.