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.

Practice

1. What does the term inversion in an array mean?

easy

A. The total number of elements in the array

B. A pair of elements where the first is greater than the second and appears before it

C. A pair of elements where the first is smaller than the second and appears before it

D. The sum of all elements in the array

Solution

1. Step 1: Understand the definition of inversion

   An inversion is when a larger number appears before a smaller number in the array.

2. Step 2: Compare options with definition

   A pair of elements where the first is greater than the second and appears before it matches this definition exactly, others describe different concepts.

3. Final Answer:

   A pair of elements where the first is greater than the second and appears before it -> Option B

4. Quick Check:

   Inversion = larger before smaller [OK]

Hint: Inversion means bigger number comes before smaller one [OK]

Common Mistakes:

• Confusing inversion with sorted order
• Thinking inversion counts equal elements
• Mixing inversion with total pairs

2. Which of the following C code snippets correctly declares a function to count inversions in an array?

easy

A. int countInversions(int arr[], int n);

B. void countInversions(int arr[], int n);

C. int countInversions(int arr, int n[]);

D. int countInversions(int *arr, int n[]);

Solution

1. Step 1: Check function signature correctness

   The function should return an integer count and take an integer array and its size as parameters.

2. Step 2: Analyze each option

   int countInversions(int arr[], int n); correctly uses int return type and parameters as int arr[] and int n. Others have wrong parameter types or return type.

3. Final Answer:

   int countInversions(int arr[], int n); -> Option A

4. Quick Check:

   Correct function signature returns int and takes int array and size [OK]

Hint: Function returns int and takes int array plus size [OK]

Common Mistakes:

• Using void return type instead of int
• Swapping array and size parameter types
• Using pointer syntax incorrectly

3. What is the output of the following C code snippet?

int arr[] = {2, 4, 1, 3, 5};
int n = 5;
int count = 0;
for(int i = 0; i < n-1; i++) {
  for(int j = i+1; j < n; j++) {
    if(arr[i] > arr[j]) count++;
  }
}
printf("%d", count);

medium

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Identify all inversion pairs in the array

   Pairs where first element is greater than second: (2,1), (4,1), (4,3). Total = 3.

2. Step 2: Confirm count variable increments correctly

   Nested loops check all pairs; count increments for each inversion found, total 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Inversions = 3 [OK]

Hint: Count pairs where left element > right element [OK]

Common Mistakes:

• Counting pairs where left < right
• Missing some inversion pairs
• Off-by-one errors in loops

4. The following code is intended to count inversions but has a bug. What is the bug?

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

medium

A. Inner loop should start from j = i + 1, not j = i

B. The count variable should be initialized outside the function

C. The comparison should be arr[i] < arr[j]

D. The function should return void instead of int

Solution

1. Step 1: Analyze loop ranges for counting pairs

   Inner loop starts at j = i, so it compares arr[i] with itself, causing incorrect counting.

2. Step 2: Correct inner loop start index

   Inner loop should start at j = i + 1 to avoid self-comparison.

3. Final Answer:

   Inner loop should start from j = i + 1, not j = i -> Option A

4. Quick Check:

   Start inner loop at i+1 to avoid self-comparison [OK]

Hint: Inner loop must start after outer loop index [OK]

Common Mistakes:

• Starting inner loop at same index as outer
• Wrong comparison operator
• Returning wrong type

5. Given the array {8, 4, 2, 1}, what is the total number of inversions? Also, explain why this number represents the worst case for inversion counting.

hard

A. 4

B. 0

C. 3

D. 6

Solution

1. Step 1: Count all inversion pairs in the array

   Pairs: (8,4), (8,2), (8,1), (4,2), (4,1), (2,1) total 6 inversions.

2. Step 2: Understand why this is worst case

   The array is sorted in descending order, so every pair is inverted, maximum inversions possible for size 4.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Descending order array has max inversions = n(n-1)/2 [OK]

Hint: Descending order array has max inversions n(n-1)/2 [OK]

Common Mistakes:

• Counting only adjacent inversions
• Forgetting pairs with elements far apart
• Confusing inversion count with array length