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
- Initialize a
counter
to keep track of the inversions. - Iterate through each element in the array using
i
. - For each
i
, iterate through the remaining elements usingj
. - Check if
arr[i]
is greater thanarr[j]
. - If the condition is satisfied, increment the
counter
. - 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.
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.
New Comment