HI i found that it Can Be Done Using BST in O(nlogn) see the
explaination & then code , let me know if m wrong or anything mising
also tryvto dry run yourself
/*
Explanation
we are constructing BST from the array elements and maintaining a
count on each node. The idea here is every parent node must maintain
the number of nodes that branched on to it's right side (right count).
The above code fails if there are equal element which cause the count
to be incremented. Equal nodes won't participate in inversions. The
count (rc) will be used to track the number of inversions.each rc say
we have these no of inversion of this number.
However, when the array is reverse sorted, the tree will be fully
right skewed. While inserting i-th node, we need to visit previous
(i-1) nodes, so the worst case complexity is no better than O(n^2).
Where as merge sort procedure doesn't depend on data to be sorted.
What ever may be the permutation of input data, merge sort will sort
the array in O(NlogN) time, so the inversion count.
*/
#include<iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
int rc;
};
node *root = NULL;
int get_inv(int val)
{
node *newnode = new node;
newnode -> data = val;
newnode -> left = NULL;
newnode -> right = NULL;
newnode -> rc = 0;
int inv = 0;
if(!root)
{
root = newnode;
return 0;
}
node *ptr = root;
node *pptr = root;
while(ptr)
{
pptr = ptr;
if(val < ptr->data)
{
inv += ptr->rc +1;
ptr = ptr->left;
}
else
{
ptr->rc++;
ptr = ptr->right;
}
}
if(val < pptr->data)
{
pptr->left = newnode;
}
else
{
pptr->right = newnode;
}
return inv;
}
int count_inv(int *array,int n)
{
int inv = 0;
for(int i=0;i<n;i++)
{
inv += get_inv(array[i]);
}
return inv;
}
int main()
{
int array[] = {3,6,1,2,4,5};
cout<<count_inv(array,6)<<endl;
return 0;
}
Thanks &Regards
Shashank Mani Narayan
Birla Institute of Technology,Mesra
Computer Science & Engineering
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
