Re: [algogeeks] Re: Finding total number of inversions in an array in O(nlogn) complexity .

[Harshal]

AC:

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

void MergeSort(vector<long>& v, long p, long r);
void Merge(vector<long> &v, long p, long q, long r);
void PrintArray(vector<long> v);

long long int count;

int main()
{
   extern long long int count;
   long n, i, t;
   vector<long> v;

   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);

   cin >> t;
   while(t--)
   {
   count = 0;
   scanf("%ld",&n);
   v.resize(n);

   for(i=0; i<n; i++)
        scanf("%ld",&v[i]);

   //cout << "The Input array is:" << endl;
   //PrintArray(v);

   MergeSort(v,0,n-1);

   //cout << "The Sorted array is:" << endl;
   //PrintArray(v);
   printf("%lld\n\n",count);//count << endl;
   }
   return 0;
}

void MergeSort(vector<long>& v, long p, long r)
{
    if(p < r)
    {
         long q = (p+r)/2;
         MergeSort(v,p,q);
         MergeSort(v,q+1,r);
         Merge(v,p,q,r);
    }
}

void Merge(vector<long>& v, long p, long q, long r)
{
    extern long long count;
    long i, j, k;
    vector<int> v1, v2;
    v1.resize(q-p+1);
    v2.resize(r-q);

    k=0;
    for(i=p; i<=q; i++)
        v1[k++] = v[i];

    k=0;
    for(i=q+1; i<=r; i++)
        v2[k++] = v[i];

    v1.push_back(INT_MAX);
    v2.push_back(INT_MAX);

    i=0; j=0;
    for(k=p; k<=r ;k++)
    {
         if(v1[i] <= v2[j])
         {
             v[k] = v1[i++];
             count += j;      /* when taking element from 1st array
Incrementing count by no of elements already taken from 2nd array
       */}
         else
             v[k] = v2[j++];
    }
}
void PrintArray(vector<int> &v)
{
    long i,n = v.size();
    for(i=0; i<n; i++)
        printf("%ld ",v[i]);
    printf("\n");
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.