This is my implementation for counting the inversions in an Array.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <math.h> | |
#define MAXSIZ 100010 | |
long long int sortandcount(long long int a[],long long int low,long long int high); | |
long long int mergeandcountsplit(long long int b[],long long int lowi,long long int midi,long long int highi); | |
int main(int argc, char const *argv[]) | |
{ | |
long long int array[MAXSIZ]/*input array*/, n/*array size*/; | |
long long int inversions,i; | |
scanf("%lld", &n); | |
for (i = 0; i < n; ++i) | |
scanf("%lld", &array[i]);/*reading*/ | |
inversions=sortandcount(array,0,n-1); | |
printf("%lld\n", inversions); | |
return 0; | |
} | |
long long int sortandcount(long long int a[],long long int low,long long int high) | |
{ | |
long long int x=0,y=0,z=0,mid=(low+high)/2; | |
if (low<high) | |
{ | |
x=sortandcount(a,low, mid); | |
y=sortandcount(a,mid+1,high); | |
z=mergeandcountsplit(a,low,mid,high); | |
} | |
return x+y+z; | |
} | |
long long int mergeandcountsplit(long long int b[],long long int lowi,long long int midi,long long int highi) | |
{ | |
long long int stepmother[MAXSIZ];/*step mother for our sorting array*/ | |
/*It's very pity that, every time step | |
mother grows his child in a sorted way | |
from an unsorted and then every time | |
the natural mother reclaims the sorted son*/ | |
/*too pity*/ | |
long long int i=lowi,j=midi+1,k=0; | |
long long int inversion_S=0; | |
while(i<=midi&&j<=highi) | |
{ | |
if (b[i]<=b[j]) | |
{ | |
stepmother[k++]=b[i++]; | |
} | |
else | |
{ | |
inversion_S+=midi-i+1;/*Birthday Party*/ | |
stepmother[k++]=b[j++]; | |
} | |
} | |
while(i<=midi) | |
stepmother[k++]=b[i++]; | |
while(j<=highi) | |
stepmother[k++]=b[j++]; | |
while(k--) | |
b[lowi+k]=stepmother[k]; | |
return inversion_S; | |
} |
I was really amazed to find that counting inversions in an array is used in collaborative filtering i.e for generating recommendations for a new user.
Now I am getting that Codejam problem called Rope Intranet which is about finding the Inversions of the second building values as the first building values will be given in a sorted order.