# Inversion of Array

Array inversion is a concept that plays a significant role in algorithms and data manipulation. In this article, we'll delve into the world of array inversion, exploring its meaning, working principles, and implementation in C++. We will cover real-world applications, examples, and analyze time and space complexities to provide a thorough understanding of this important topic.

#### What is Array Inversion?

Array inversion refers to the process of counting the number of pairs of indices (i, j) such that i < j and array[i] > array[j]. In simpler terms, it quantifies the number of elements that are out of order in relation to each other.

#### Working of Array Inversion:

- Pair Comparison: For each pair of indices (i, j) in the array where i < j, check if array[i] is greater than array[j].
- Counting Inversions: Increment a counter whenever array[i] is greater than array[j], indicating an inversion.

Code

```
// C++ Code
#include <iostream>
// Function to invert an array
void invertArray(int arr[], int length) {
for (int i = 0; i < length / 2; ++i) {
// Swap elements at positions i and length-i-1
std::swap(arr[i], arr[length - i - 1]);
}
}
int main() {
// Example array
int myArray[] = {1, 2, 3, 4, 5};
int arrayLength = sizeof(myArray) / sizeof(myArray[0]);
// Print original array
std::cout << "Original array: ";
for (int i = 0; i < arrayLength; ++i) {
std::cout << myArray[i] << " ";
}
std::cout << std::endl;
// Invert the array
invertArray(myArray, arrayLength);
// Print inverted array
std::cout << "Inverted array: ";
for (int i = 0; i < arrayLength; ++i) {
std::cout << myArray[i] << " ";
}
std::cout << std::endl;
return 0;
}
```

The invertArray function is responsible for reversing the order of elements in the array. The std::swap function is used to swap elements at positions i and length-i-1 within the loop. The main function demonstrates how to use this function with a sample array.

Here's the step-by-step breakdown for the example array [1, 2, 3, 4, 5]:

- Original array: [1, 2, 3, 4, 5]
- After the first iteration of the loop: [5, 2, 3, 4, 1]
- After the second iteration: [5, 4, 3, 2, 1]

Now, the array is inverted. The logic is similar to the Python example, where elements are swapped starting from both ends and moving towards the middle of the array.

#### Example

Let's implement a simple C++ program to calculate the number of inversions in an array.

```
// C++ Code
#include <iostream>
#include <vector>
class ArrayInversionCounter {
private:
long long mergeAndCount(std::vector<int>& arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
std::vector<int> left(n1), right(n2);
for (int i = 0; i < n1; i++)
left[i] = arr[l + i];
for (int j = 0; j < n2; j++)
right[j] = arr[m + 1 + j];
long long count = 0;
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
count += n1 - i;
}
}
while (i < n1)
arr[k++] = left[i++];
while (j < n2)
arr[k++] = right[j++];
return count;
}
long long mergeSortAndCount(std::vector<int>& arr, int l, int r) {
long long count = 0;
if (l < r) {
int m = l + (r - l) / 2;
count += mergeSortAndCount(arr, l, m);
count += mergeSortAndCount(arr, m + 1, r);
count += mergeAndCount(arr, l, m, r);
}
return count;
}
public:
long long countInversions(std::vector<int>& arr) {
return mergeSortAndCount(arr, 0, arr.size() - 1);
}
};
int main() {
ArrayInversionCounter inversionCounter;
std::vector<int> arr = {1, 20, 6, 4, 5};
long long inversions = inversionCounter.countInversions(arr);
std::cout << "Array Inversions: " << inversions << std::endl;
return 0;
}
```

##### Output

`Array Inversions: 5`

##### Explanation

- The code now encapsulates the array inversion counting logic within the ArrayInversionCounter class.
- The mergeSortAndCount function recursively divides the array and counts inversions during the merge process.
- The mergeAndCount function counts inversions when merging two sorted subarrays.
- In the main function, an instance of ArrayInversionCounter is created, and the countInversions method is invoked on the array {1, 20, 6, 4, 5}.
- The output, "Array Inversions: 5", indicates that there are 5 inversions in the given array.

#### Time and Space Complexity

- Time Complexity: The time complexity of the provided algorithm is O(n log n) due to the merge sort.
- Space Complexity: The space complexity is O(n) as additional space is required for merging subarrays.

#### Use Cases

- Sorting Algorithms: Inversions are crucial in analyzing and understanding the performance of sorting algorithms.
- Financial Data Analysis: Array inversion can be applied in analyzing financial time series data to identify anomalies.
- Data Compression: Inversions play a role in algorithms for data compression, where patterns of disorder may indicate compressible structures.

Array inversion is a fundamental concept with applications ranging from algorithm analysis to data compression. Understanding array inversion equips developers with insights that are valuable in algorithm design and real-world data analysis.