C Exercises: Count the number of inversion in a given array

Last update on July 31 2025 13:02:29 (UTC/GMT +8 hours)

66. Count Inversions in Array

Write a program in C to count the number of inversions in a given array.

Expected Output :
The given array is : 1 9 6 4 5
The inversions are: (9, 6) (9, 4) (9, 5) (6, 4) (6, 5)
The number of inversion can be formed from the array is: 5

The problem involves writing a C program to count the number of inversions in a given array. An inversion is a pair of elements where the first element is greater than the second element and appears before it in the array. The program should identify and count all such pairs, then display both the inversions and their total count.

Visual Presentation:

C Exercises: Count the number of inversion in a given array.

Sample Solution:

C Code:

#include <stdio.h>

// Function to count the number of inversions in the array
int inv_count(int arr1[], int n) {
int inversionCtr = 0;
printf("The inversions are: ");

    // Loop through each pair of elements to find inversions
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
            // If a pair forms an inversion, print it and increment the counter
if (arr1[i] > arr1[j]) {
printf("(%d, %d)  ", arr1[i], arr1[j]);
inversionCtr++;
            }
        }
    }
return inversionCtr; // Return the total count of inversions
}

int main() {
int arr1[] = { 1, 9, 6, 4, 5 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int i;

    // Print the original array
printf("The given array is :  ");
for(i = 0; i < n; i++) {
printf("%d  ", arr1[i]);
    } 
printf("\n");

    // Count and display the number of inversions in the array
printf("\nThe number of inversions that can be formed from the array is:  %d", inv_count(arr1, n));
return 0;
}

Sample Output:

The given array is :  1  9  6  4  5  
The inversions are: (9, 6)  (9, 4)  (9, 5)  (6, 4)  (6, 5)  
The number of inversion can be formed from the array is:  5

Flowchart:/p> Count the number of inversion in a given array

For more Practice: Solve these Related Problems:

Write a C program to count inversions in an array using a modified merge sort algorithm.
Write a C program to count inversions recursively and then output all inversion pairs.
Write a C program to count the number of inversions in an array using brute-force nested loops.
Write a C program to compute the inversion count and then compare it with the sorted order of the array.

Go to:

PREV : Product Array Except Self.
NEXT : Search in Row & Column Sorted Matrix.

C Programming Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.