Sunday 22 February 2015

Inversion count (using maerge sort)

Inversion count





#include<bits/stdc++.h>

using namespace std;

void merg(long long int st,long long int mm,long long int en);

long long int a[10000001],b[10000001],inc=0;

void merge_sort(long long int st,long long int en)
{
  int m;
  if(en>st)
  {
   m=(st+en)/2;
   merge_sort(st,m);
   merge_sort(m+1,en);
   merg(st,m,en);
  }
}

void merg(long long int st,long long int m,long long int en)
{

 long long int f=st,k=st,sst=m+1,i;
 while(f<=m && sst<=en)
 {
   if(a[f]<a[sst])          ///sst= second start
    {b[k++]=a[f++];}
   else
    {b[k++]=a[sst++];
          if(a[f]!=a[sst])  inc=inc+(m-f+1);  ///this line makes merge sort to inversion count
    }
 }

  if(f>m)
   for(i=sst;i<=en;i++)
   b[k++]=a[i];

  else
  for(i=f;i<=m;i++)
  b[k++]=a[i];

  for(i=st;i<=en;i++)
  a[i]=b[i];
}


int main()
{
int t;
cin>>t;
 while(t--)
 {
  long long int n,i;
  cin>>n;
  inc=0;
   for(i=0;i<n;i++)
   cin>>a[i];
   merge_sort(0,n-1);
   cout<<inc<<endl;
 }
return 0;
}

No comments:

Post a Comment

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...