Count Inversions in Array in DSA C - Build from Scratch

Count Inversions in Array

📖 Scenario: Imagine you have a list of numbers representing the order of books on a shelf. You want to find out how many pairs of books are out of order compared to their correct sorted order. This count is called the number of inversions.

🎯 Goal: Build a program that counts the number of inversions in an array of integers. An inversion is a pair of positions where the earlier number is greater than the later number.

📋 What You'll Learn

Create an array called arr with the exact values: 2, 4, 1, 3, 5

Create an integer variable called n and set it to the size of arr

Write a function called countInversions that takes the array arr and its size n and returns the number of inversions

Print the number of inversions using printf

💡 Why This Matters

🌍 Real World

Counting inversions helps measure how far a list is from being sorted, useful in sorting algorithms and data analysis.

💼 Career

Understanding inversion counting is important for software engineers working on algorithms, data processing, and performance optimization.

1

Create the array

Create an integer array called arr with these exact values: 2, 4, 1, 3, 5. Also create an integer variable called n and set it to 5.

DSA C

# Create the array arr and variable n
// Your code here

Hint

Use int arr[] = {2, 4, 1, 3, 5}; to create the array and int n = 5; for the size.

2

Write the countInversions function

Write a function called countInversions that takes an integer array arr and its size n as parameters. Inside, create an integer variable count initialized to 0. Use two nested for loops with variables i and j to check all pairs where i < j. If arr[i] > arr[j], increment count. Return count at the end.

DSA C

int arr[] = {2, 4, 1, 3, 5};
int n = 5;

// Write the countInversions function below
// Your code here

Hint

Use nested loops to compare each pair and count when the first number is bigger than the second.

3

Call the function and store the result

Call the function countInversions with the array arr and size n. Store the returned value in an integer variable called result.

DSA C

int arr[] = {2, 4, 1, 3, 5};
int n = 5;

int countInversions(int arr[], int n) {
    int count = 0;
    for (int i = 0; i  arr[j]) {
                count++;
            }
        }
    }
    return count;
}

// Call countInversions and store the result in variable result
// Your code here

Hint

Use int result = countInversions(arr, n); to call the function and save the answer.

4

Print the number of inversions

Print the value of the variable result using printf with the format string "Number of inversions: %d\n".

DSA C

int arr[] = {2, 4, 1, 3, 5};
int n = 5;

int countInversions(int arr[], int n) {
    int count = 0;
    for (int i = 0; i  arr[j]) {
                count++;
            }
        }
    }
    return count;
}

int result = countInversions(arr, n);

// Print the result below
// Your code here

Hint

Use printf("Number of inversions: %d\n", result); inside main to show the answer.