Count inversions in an array

Inversion Means:=>

Problem statement:- Program to Count inversions in an array.

Example:-

              Input : Given

                                 size=5

                                 arr[]=[1,2,3,5,4] 

             Output:  All the inversions are:(5,4)

                           Number of Inversions is  1               

Data requirement:-

   Input Data:- size, arr

  Output Data:-arr,count

  

  Additional Data:- i,j

Program in C

Here is the source code of the C Program to Count inversions in an array.

Code:

#include<stdio.h>

main()

{

    printf("Enter the size of the array:");

    int size;

    scanf("%d",&size);

    int arr[size];

    int i,j,p;

    printf("Enter the Element of the array:\n");

    for(i=0;i<size;i++)

    {

        scanf("%d",&arr[i]);

    }

    int count=0;

    printf("All the inversions are:");

     for(i=0;i<size-1;i++)

    {

         for(j=i+1;j<size;j++)

          {

              if(arr[i]>arr[j])

              {

                 printf("(%d, %d) ",arr[i],arr[j]);

                 count++;

              }

          }}

              if(count==0)

                printf("(0)");

            else if(count==1)

                printf("\nNumber of Inversions is %d",count);

              else

                printf("\nNumber of Inversions Are %d",count);

}

Input/Output:

Enter the size of the array:5

Enter the Element of the array:

1 2 3 5 4

All the inversions are:(5,4)

Number of Inversions is 1

Program in C++

Here is the source code of the C++ Program to Count inversions in an array.

Code:

#include<iostream>

using namespace std;

int main()

{

    cout<<"Enter the size of the array:";

    int size;

    cin>>size;

    int arr[size];

    int i,j;

    cout<<"Enter the Element of the array:\n";

    for(i=0;i<size;i++)

    {

        cin>>arr[i];

    }

    int count=0;

    cout<<"All the inversions are:";

     for(i=0;i<size-1;i++)

    {

         for(j=i+1;j<size;j++)

          {

              if(arr[i]>arr[j])

              {

                 cout<<"("<<arr[i]<<","<<arr[j]<<")";

                 count++;

              }

          }}

              if(count==0)

                cout<<"(0)";

              else if(count==1)

                cout<<"\nNumber of Inversions is "<<count;

              else

                cout<<"\nNumber of Inversions are "<<count;

}

Input/Output:

Enter the size of the array:6

Enter the Element of the array:

5 6 8 9 2 3

All the inversions are:(5, 2) (5, 3) (6, 2) (6, 3) (8, 2) (8, 3) (9, 2) (9, 3)

Number of Inversions Are 8

Program in Java

Here is the source code of the Java Program to Count inversions in an array.

Code:

import java.util.Scanner;

public class NumberOfInversions {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

  System.out.println("Enter the size of the array:");

     int size,i,j;

     size=sc.nextInt();

     int arr[ ]=new int[size];

  System.out.println("Enter the Element of the array:");

      for(i=0;i<size;i++)

     {

         arr[i]=sc.nextInt();

     }

      int count=0;

      System.out.print("All the inversions are:");

       for(i=0;i<size-1;i++)

      {

           for(j=i+1;j<size;j++)

            {

                if(arr[i]>arr[j])

                {

                System.out.print("("+arr[i]+","+arr[j]+")");

                    count++;

                }

            }}

                if(count==0)

                System.out.print("(0)");

                else if(count==1)

                System.out.print("\nNumber of Inversions is "+count);

                else

                System.out.print("\nNumber of Inversions are "+count);

                sc.close();

}

}

Input/Output:

Enter the size of the array:

5

Enter the Element of the array:

5 4 6 8 7

All the inversions are:(5,4)(8,7)

Number of Inversions are 2

Program in Python

Here is the source code of the Python Program to Count inversions in an array.

Code:

arr=[]

size = int(input("Enter the size of the array: "))

print("Enter the Element of the array:")

for i in range(0,size):

    num = int(input())

    arr.append(num)

count=0

print("All the inversions are:")

for i in range(0,size-1):

    for j in range(i+1, size):

        if arr[i]>arr[j]:

            print("(",arr[i],",",arr[j],")")

            count+=1

if count==0:

     print("(0)")

elif count==0:

     print("\nNumber of Inversions is ",count)

else:

    print("\nNumber of Inversions are ",count)

Input/Output:

Enter the size of the array: 4

Enter the Element of the array:

10

12

14

13

All the inversions are:

( 14 , 13 )

Number of Inversions are  1

More:-

C/C++/Java/Python Practice Question