Count the number of inversions in an array using the C programming language

Count the number of inversions in an array using the C programming language

Counting inversions in an array involves finding the number of pairs (i, j) such that i < j and array[i] > array[j]. This can be done using various algorithms, with the merge sort algorithm being a popular choice due to its efficiency.

Code:

#include <stdio.h>

long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) {
int i = left;
int j = mid;
int k = left;
long long inversions = 0;

while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inversions += mid - i;
}
}

while (i <= mid - 1) {
temp[k++] = arr[i++];
}

while (j <= right) {
temp[k++] = arr[j++];
}

for (i = left; i <= right; i++) {
arr[i] = temp[i];
}

return inversions;
}

long long mergeSortAndCount(int arr[], int temp[], int left, int right) {
long long inversions = 0;
if (left < right) {
int mid = left + (right - left) / 2;

inversions += mergeSortAndCount(arr, temp, left, mid);
inversions += mergeSortAndCount(arr, temp, mid + 1, right);

inversions += mergeAndCount(arr, temp, left, mid + 1, right);
}
return inversions;
}

long long countInversions(int arr[], int n) {
int *temp = (int *)malloc(sizeof(int) * n);
return mergeSortAndCount(arr, temp, 0, n - 1);
}

int main() {
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);

long long inversions = countInversions(arr, n);

printf("Number of inversions: %lld\n", inversions);

return 0;
}

 

In this program, the mergeAndCount function merges two subarrays and counts the inversions during the merging process. The mergeSortAndCount function recursively divides the array and counts inversions by merging subarrays. Finally, the countInversions function initializes temporary memory and calls the merge sort function.

Make sure to include the necessary headers and libraries, and you can replace the arr array in the main function with your own array to count the inversions for a specific array.

 

Explanation:

#include <stdio.h>

This line includes the standard input/output library, which provides functions like printf and scanf.

long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) {

Here, a function named mergeAndCount is defined. It takes five arguments: arr (the original array), temp (a temporary array for merging), left (the starting index of the left subarray), mid (the ending index of the left subarray and the starting index of the right subarray), and right (the ending index of the right subarray).

int i = left;
int j = mid;
int k = left;
long long inversions = 0;

Several variables are declared and initialized:

• i, j, and k are index pointers used for iterating through the subarrays.

• inversions is a variable used to keep track of the number of inversions found during the merge.

while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
inversions += mid - i;
}
}

This loop iterates through the two subarrays, comparing elements at indices i and j. If an element in the left subarray (arr[i]) is less than or equal to the element in the right subarray (arr[j]), it's placed in the temp array. If the right element is smaller, an inversion is found, and the count is increased by the difference mid - i, as all remaining elements in the left subarray are greater than arr[j].

while (i <= mid - 1) {
temp[k++] = arr[i++];
}

while (j <= right) {
temp[k++] = arr[j++];
}

These loops handle any remaining elements in the subarrays that haven't been processed in the previous loop.

for (i = left; i <= right; i++) {
arr[i] = temp[i];
}

This loop copies the sorted elements from the temp array back into the original arr array.

return inversions;
}

The mergeAndCount function returns the number of inversions found during the merge.

long long mergeSortAndCount(int arr[], int temp[], int left, int right) {

The mergeSortAndCount function is defined. It's the main driver for the merge sort algorithm with inversion counting. It takes four arguments: arr (the original array), temp (temporary array), left (starting index of the subarray), and right (ending index of the subarray).

long long inversions = 0;
if (left < right) {

The inversions variable is initialized to 0. Then, it checks if there's more than one element in the subarray (left < right). If so, the following steps are executed:

int mid = left + (right - left) / 2;

The midpoint index of the subarray is calculated. This will be used to divide the subarray into two halves.

inversions += mergeSortAndCount(arr, temp, left, mid);
inversions += mergeSortAndCount(arr, temp, mid + 1, right);

The mergeSortAndCount function is recursively called on the left and right halves of the subarray. The returned counts of inversions are added to the inversions variable.

inversions += mergeAndCount(arr, temp, left, mid + 1, right);

The mergeAndCount function is called to merge the two sorted halves and count any inversions that occur during the merge. The returned count is added to the inversions variable.

}
return inversions;
}

The mergeSortAndCount function returns the total number of inversions found in the subarray.

long long countInversions(int arr[], int n) {
int *temp = (int *)malloc(sizeof(int) * n);
return mergeSortAndCount(arr, temp, 0, n - 1);
}

The countInversions function initializes memory for the temp array and then calls the mergeSortAndCount function on the entire array.

int main() {
int arr[] = {8, 4, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);

long long inversions = countInversions(arr, n);

printf("Number of inversions: %lld\n", inversions);

return 0;
}

In the main function, an example array arr is defined. Its size n is calculated using the sizeof operator. The countInversions function is called on the array, and the result is printed to the console.

Please note that the program uses dynamic memory allocation (malloc) for the temporary array. Don't forget to include the necessary headers (#include <stdlib.h>) for memory allocation functions. Also, ensure to free the allocated memory when you're done with it using free(temp).

 

Algorithm:

1. mergeAndCount Function:

   • This function takes the original array arr, a temporary array temp, and three indices: left, mid, and right.

   • Initialize variables i, j, and k to left, mid, and left, respectively. Initialize inversions to 0.

   • Iterate while both i and j are within their respective subarrays:

     • If arr[i] is less than or equal to arr[j], copy arr[i] to temp[k], and increment both i and k.

     • Otherwise, copy arr[j] to temp[k], increment both j and k, and add mid - i to inversions.

   • Copy any remaining elements from both subarrays to temp.

   • Copy the sorted elements from temp back to arr.

   • Return the inversions count.

2. mergeSortAndCount Function:

   • This function takes the original array arr, a temporary array temp, and two indices: left and right.

   • Initialize inversions to 0.

   • If left is less than right (i.e., there are more than one element in the subarray), do the following:

     • Calculate the midpoint index mid.

     • Recursively call mergeSortAndCount on the left half (from left to mid).

     • Recursively call mergeSortAndCount on the right half (from mid + 1 to right).

     • Add the result of mergeAndCount called on the entire subarray to inversions.

   • Return the total inversions count.

3. countInversions Function:

   • This function takes the original array arr and its size n.

   • Allocate memory for the temporary array temp.

   • Call mergeSortAndCount on the entire array and return the result.

4. Main Function:

   • In the main function, an example array arr is defined.

   • Calculate the size n of the array.

   • Call countInversions on the array to count the inversions.

   • Print the number of inversions.

The algorithm essentially uses the divide-and-conquer approach of merge sort to recursively divide the array into smaller subarrays until individual elements are reached. During the merging step, it counts the inversions by tracking how many times elements in the left subarray are greater than elements in the right subarray. The counts from all merging steps are added up to get the total number of inversions in the array.

 

Time Complexity:

The time complexity of the above C program that counts the number of inversions in an array using the merge sort algorithm is O(n log n), where 'n' is the number of elements in the array.

Here's the breakdown of the time complexity:

1. Merge Sort Time Complexity: The merge sort algorithm, used to sort the array and count inversions, has a time complexity of O(n log n). This is because in each recursion, the array is divided into two halves, and the merging step takes linear time proportional to the size of the subarrays being merged. The recurrence relation for merge sort's time complexity is T(n) = 2T(n/2) + O(n), which leads to O(n log n) time complexity.

2. Counting Inversions Time Complexity: The merging step in the merge sort algorithm takes linear time O(n) for each merge, and it's executed for every level of recursion. Since the depth of recursion is log(n) for an array of size n, the total time complexity for counting inversions is O(n log n).

Combining the time complexity of sorting (O(n log n)) with the time complexity of counting inversions (O(n log n)), we get an overall time complexity of O(n log n) for the entire program.

 

Space Complexity:

The space complexity of the above C program that counts the number of inversions in an array using the merge sort algorithm is O(n), where 'n' is the number of elements in the array.

Here's why:

1. Input Array and Temporary Array: The main space usage in the program is due to the input array (arr) and the temporary array (temp) used for merging. Both of these arrays have a size of 'n', which means they each consume O(n) space.

2. Recursion Stack: The space complexity also includes the memory used by the recursion stack during the recursive merge sort process. At any point during recursion, the maximum number of function calls that can be active is log(n) (the depth of the recursion tree). This contributes a space complexity of O(log n).

3. Other Variables: The program uses a few additional variables like indices (i, j, k, left, right, mid) and the inversion count variable (inversions). These variables are used to keep track of positions and counts during the algorithm's execution. However, these variables have a constant amount of memory usage and do not depend on the input size 'n'.

Putting it all together, the dominant factor in the space complexity is the usage of the input array (arr) and the temporary array (temp), both of which contribute O(n) to the space complexity. The additional variables and recursion stack usage have a smaller, logarithmic impact compared to the array sizes. Thus, the overall space complexity of the program is O(n).

Thank You