Posted on by Kalkicode
Code Array

# Count inversions in an array

The task of counting inversions in an array involves determining how far the array is from being sorted. An inversion occurs when a pair of elements in the array is in the wrong order. This concept has applications in various scenarios, such as sorting algorithms and similarity calculations. In this article, we will delve into the problem of counting inversions, mentioned a detailed explanation, outline an effective approach, offer pseudocode and an algorithm, explain the output, analyze time complexity, and present concise code examples.

## Problem Statement

Given an array, the goal is to count the number of inversions in the array. An inversion occurs when `arr[i] > arr[j]` for any `i < j`.

## Example

Consider the array: Array: [1, -4, 7, 6, 4, 5, 8]

In this array, there are 6 inversion pairs: (-4, 7), (-4, 6), (-4, 5), (-4, 8), (7, 6), and (6, 5).

## Approach to Solve the Problem

A simple approach to solve this problem involves using two nested loops. For each element `arr[i]`, we iterate through the remaining elements to check if there is any element `arr[j]` (where `j > i`) such that `arr[i] > arr[j]`. If such a condition is met, we increment a counter to keep track of the inversions.

## Pseudocode

``````count_inversions(arr, size):
counter = 0
for i from 0 to size - 2:
for j from i + 1 to size - 1:
if arr[i] > arr[j]:
increment counter

print "Array:", arr
print "Inversions pair:", counter``````

## Algorithm Explanation

1. Initialize a `counter` to keep track of the inversions.
2. Iterate through each element in the array using `i`.
3. For each `i`, iterate through the remaining elements using `j`.
4. Check if `arr[i]` is greater than `arr[j]`.
5. If the condition is satisfied, increment the `counter`.
6. Print the original array and the inversion count.

## Code Solution

``````//C Program
//Count inversions in an array
#include <stdio.h>
//print the array elements
void display(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
printf("  %d", arr[i]);
}
}
//Count all inversions pairs in given array
void count_inversions(int arr[], int size)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter++;
}
}
}
printf("\n Array : ");
display(arr, size);
printf("\n Inversions pair : %d\n", counter);
}
int main()
{
//Define array elements
int arr[] = {
1,
-4,
7,
6,
4,
5,
8
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
count_inversions(arr, size);
return 0;
}``````

#### Output

`````` Array :   1  -4  7  6  4  5  8
Inversions pair : 6``````
``````// Java program
// Count inversions in an array
class MyArray
{
//print given array elements
public void display(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
System.out.print(" " + arr[i]);
}
}
//Count all inversions pairs in given array
public void count_inversions(int[] arr, int size)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter++;
}
}
}
System.out.print("\n Array : ");
display(arr, size);
System.out.print("\n Inversions pair : " + counter + "\n");
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array elements
int[] arr = {
1,
-4,
7,
6,
4,
5,
8
};
//Count size of array
int size = arr.length;
obj.count_inversions(arr, size);
}
}``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ program
// Count inversions in an array
class MyArray
{
public:
//print given array elements
void display(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
cout << " " << arr[i];
}
}
//Count all inversions pairs in given array
void count_inversions(int arr[], int size)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter++;
}
}
}
cout << "\n Array : ";
this->display(arr, size);
cout << "\n Inversions pair : " << counter << "\n";
}
};
int main()
{
MyArray obj = MyArray();
int arr[] = {
1 , -4 , 7 , 6 , 4 , 5 , 8
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.count_inversions(arr, size);
return 0;
}``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````//Include namespace system
using System;
// C# program
// Count inversions in an array
class MyArray
{
//print given array elements
public void display(int[] arr, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
Console.Write(" " + arr[i]);
}
}
//Count all inversions pairs in given array
public void count_inversions(int[] arr, int size)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter++;
}
}
}
Console.Write("\n Array : ");
display(arr, size);
Console.Write("\n Inversions pair : " + counter + "\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr = {
1 , -4 , 7 , 6 , 4 , 5 , 8
};
//Count size of array
int size = arr.Length;
obj.count_inversions(arr, size);
}
}``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````<?php
// Php program
// Count inversions in an array
class MyArray
{
//print given array elements
public	function display( \$arr, \$size)
{
\$i = 0;
for (\$i = 0; \$i < \$size; \$i++)
{
echo " ". \$arr[\$i];
}
}
//Count all inversions pairs in given array
public	function count_inversions( \$arr, \$size)
{
\$counter = 0;
for (\$i = 0; \$i < \$size; ++\$i)
{
for (\$j = \$i + 1; \$j < \$size; ++\$j)
{
if (\$arr[\$i] > \$arr[\$j])
{
//When get a new inversions pair
\$counter++;
}
}
}
echo "\n Array : ";
\$this->display(\$arr, \$size);
echo "\n Inversions pair : ". \$counter ."\n";
}
}

function main()
{
\$obj = new MyArray();
//Define array elements
\$arr = array(1, -4, 7, 6, 4, 5, 8);
//Count size of array
\$size = count(\$arr);
\$obj->count_inversions(\$arr, \$size);
}
main();``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````// Node Js program
// Count inversions in an array
class MyArray
{
//print given array elements
display(arr, size)
{
var i = 0;
for (i = 0; i < size; i++)
{
process.stdout.write(" " + arr[i]);
}
}
//Count all inversions pairs in given array
count_inversions(arr, size)
{
var counter = 0;
for (var i = 0; i < size; ++i)
{
for (var j = i + 1; j < size; ++j)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter++;
}
}
}
process.stdout.write("\n Array : ");
this.display(arr, size);
process.stdout.write("\n Inversions pair : " + counter + "\n");
}
}

function main()
{
var obj = new MyArray();
//Define array elements
var arr = [1, -4, 7, 6, 4, 5, 8];
//Count size of array
var size = arr.length;
obj.count_inversions(arr, size);
}
main();``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````#  Python 3 program
#  Count inversions in an array
class MyArray :
# print given array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

# Count all inversions pairs in given array
def count_inversions(self, arr, size) :
counter = 0
i = 0
while (i < size) :
j = i + 1
while (j < size) :
if (arr[i] > arr[j]) :
# When get a new inversions pair
counter += 1

j += 1

i += 1

print("\n Array : ", end = "")
self.display(arr, size)
print("\n Inversions pair : ", counter ,"\n", end = "")

def main() :
obj = MyArray()
# Define array elements
arr = [1, -4, 7, 6, 4, 5, 8]
# Count size of array
size = len(arr)
obj.count_inversions(arr, size)

if __name__ == "__main__": main()``````

#### Output

`````` Array :   1  -4  7  6  4  5  8
Inversions pair :  6``````
``````#  Ruby program
#  Count inversions in an array
class MyArray

# print given array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
end
# Count all inversions pairs in given array
def count_inversions(arr, size)

counter = 0
i = 0
while (i < size)

j = i + 1
while (j < size)

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

# When get a new inversions pair
counter += 1
end
j += 1
end
i += 1
end
print("\n Array : ")
self.display(arr, size)
print("\n Inversions pair : ", counter ,"\n")
end
end
def main()

obj = MyArray.new()
# Define array elements
arr = [1, -4, 7, 6, 4, 5, 8]
# Count size of array
size = arr.length
obj.count_inversions(arr, size)
end
main()``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6
``````
``````// Scala program
// Count inversions in an array
class MyArray
{
//print given array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
}
//Count all inversions pairs in given array
def count_inversions(arr: Array[Int], size: Int): Unit = {
var counter: Int = 0;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr(i) > arr(j))
{
//When get a new inversions pair
counter += 1;
}
j += 1;
}
i += 1;
}
print("\n Array : ");
display(arr, size);
print("\n Inversions pair : " + counter + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array elements
var arr: Array[Int] = Array(1, -4, 7, 6, 4, 5, 8);
//Count size of array
var size: Int = arr.length;
obj.count_inversions(arr, size);
}
}``````

#### Output

`````` Array :  1 -4 7 6 4 5 8
Inversions pair : 6``````
``````// Swift program
// Count inversions in an array
class MyArray
{
//print given array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
//Count all inversions pairs in given array
func count_inversions(_ arr: [Int], _ size: Int)
{
var counter: Int = 0;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr[i] > arr[j])
{
//When get a new inversions pair
counter += 1;
}
j += 1;
}
i += 1;
}
print("\n Array : ", terminator: "");
self.display(arr, size);
print("\n Inversions pair : ", counter ,"\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define array elements
let arr: [Int] = [1, -4, 7, 6, 4, 5, 8];
//Count size of array
let size: Int = arr.count;
obj.count_inversions(arr, size);
}
main();``````

#### Output

`````` Array :   1  -4  7  6  4  5  8
Inversions pair :  6``````

## Time Complexity Analysis

The algorithm employs two nested loops to compare each element with the remaining elements. This results in a time complexity of O(n^2), where `n` is the size of the array. As a result, the algorithm becomes inefficient for larger arrays.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post