Programming Geek
Rated 4.7/5 based on 1446 reviews

Program for Counting Inversion in an Array

Number of an inversion in array is the number of pair(a[i],a[j]) of elements such that i < j and a[i]  > a[j]. For an example if we have a list of element 2 3 6 9 1 then number of inversion is 4 and the pairs are   (2,1),  (3,1),  (6,1)  and  (9,1).

Algorithms :

Approach 1 : The naive algorithm for this problem is to use two loops and count all the inversion. The complexity of this approach would be O(n^2). Though for small number of input, it runs quickly but for large value of n, it takes much time.


Approach 2 :
                     
                   Divide      :  Divide the array in two parts a[0] to a[n/2] and a[n/2+1] to a[n].
                 
                   Conquer  :  Conquer the sub-problem by solving them recursively.

                  Combine  :  Combine the sub-problem to get the final result.

This algorithm is based on Divide and Conquer paradigm. It is implemented using merge sort. In this approach the time complexity will be O(n log(n)) . Actually in divide step we divide the problem in two parts. And then two parts are solved recursively. The key concept is two count the number of inversion in merge procedure. In merge procedure we pass two sub-list. The element is sorted and inversion is found as follows :

                1) Set count=0,0,i=left,j=mid. C is the sorted list.
                2) Traverse list1 and list2 until mid element  or right element is encountered .
                3) Compare list1[i] and list[j].
                        i) If list1[i]<=list2[j]
                              c[k++]=list1[i++]
                          else
                              c[k++]=list2[j++]
                              count = count + mid-i;
               4) add rest elements of list1 and list2 in c.
               5) copy sorted list c back to original list.
               6) return count.

Key  concept : If an element of list two is greater than an element of list1 than all the remaining element of list1 are greater than this element. That's why we increment count by mid-i. This recursively sort the list and find the number of inversion.

Implementation of naive algorithm :


//count number of inversion using naive approach
/**
*
*@author VIKASH VIK VIKKU VIKASHVVERMA
* 
*/

#include<stdio.h>

int findinversion(int a[],int n)
{
 int i,j,count=0;
 
 for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
       {
   if(a[i]>a[j])
   count++;
    }
 }
 return count;
}

void main()
{
 int n,*a,i;
 printf("Enter nuber of elements : ");
 scanf("%d",&n);
 printf("Enter %d elements : ",n);
 a=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 printf("Number of inversion = %d",findinversion(a,n));
 
}



Implementation of approach 2 (Divide and Conquer ) :

C implementation :

#include<stdio.h>

int mergesort(int arr[],int l,int r);
int merge(int arr[],int l,int m,int r);


int findinv(int a[], int n)
{
 return mergesort(a,0,n);
}


void main()
{
 int n,*a,i;
 printf("Enter nuber of elements : ");
 scanf("%d",&n);
 printf("Enter %d elements : ",n);
 a=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&a[i]);
 printf("Number of inversion = %d",findinv(a,n));
 
}

//merge 
int merge(int arr[],int l,int m,int r)
{
 int len,i,j,k,*c,count=0;
 len=r-l+1;
 c=(int*)malloc(sizeof(int)*len);
 i=0;
 j=l;
 k=m;
 while(j<=m-1 && k<=r)
 {
  if(arr[j]<=arr[k])
  {
   c[i++]=arr[j++];
   
  }
  else
  {
   c[i++]=arr[k++];
   count+=m-j;
   
  }
  
 }
 
 while(j<=m-1)
 {
  c[i++]=arr[j++];
 }
 
 while(k<=r)
 {
  c[i++]=arr[k++];
 }
 i=0;
 while(l<=r)
 {
  arr[l++]=c[i++];
 }
 
 return count;
}


//mergesort
int mergesort(int arr[],int l,int r)
{ int count=0;
 int m=(l+r)/2;
 if(l<r)
 {
  count+=mergesort(arr,l,m);
  count+=mergesort(arr,m+1,r);
  count+=merge(arr,l,m+1,r);
  
 }
 
 return count;
}





JAVA implementation :
import java.util.*;


class InversionCount
{
 public static void main(String... v)
 {
   Scanner sc=new Scanner(System.in);
   System.out.print("Enter number of elements : ");
   int n=sc.nextInt();
   System.out.print("Enter "+n+" elements :");
   int[] a=new int[n];
   for(int i=0;i<n;i++)
    a[i]=sc.nextInt();
    System.out.println("\nNumber of Inversion = "+mergeSort(a,0,n-1));;
 }
 
  static long mergeSort(int a[],int left,int right)
  {
  int mid;
  long  count = 0;
       if (right > left)
      {
   mid = (right + left)/2;
   count  = mergeSort(a, left, mid);
   count += mergeSort(a,  mid+1, right);
  
   
  count += Merge(a, left, mid+1, right);
   }
  return count;
  }
  
  static long Merge(int a[],int l,int m,int r)
  {
  
  int length=r-l+1;
  int c[]=new int[length];
  int i=0,j=l,k=m;
  long count=0;
  while(j<=m-1&&k<=r)
  {
   if(a[j]<=a[k])
   {
    c[i]=a[j];
    i++;j++;
   }
   else
   {
    c[i]=a[k];
    count+=m-j;
    i++;k++;
   }
  }
  
  while(j<=m-1)
  {
   c[i]=a[j];
   i++;j++;
  }
  
  while(k<=r)
  {
   c[i]=a[k];
   i++;
   k++;
  }
  i=0;
  while(l<=r)
  {
   a[l]=c[i];
   l++;
   i++;
  }
  return count;
  
  }
  
}





No comments :

Post a Comment