Display Inversions pairs in array
The problem is to find and display all inversion pairs in an array. An inversion pair is a pair of elements in the array such that the element at the left index is greater than the element at the right index. In other words, for a pair of indices (i, j) where i < j, if arr[i] > arr[j], then it forms an inversion pair.
Example
Consider the following array:
[1, 7, 6, 4, 5, 9, 8]
The inversion pairs in this array are:
(7, 6)
(7, 4)
(7, 5)
(6, 4)
(6, 5)
(9, 8)
Idea to Solve the Problem
To find inversion pairs in the array, we can use a simple nested loop approach. We iterate through the array with two loops, one outer loop and one inner loop. For each pair of elements (arr[i], arr[j]), where i < j, we check if arr[i] > arr[j]. If this condition is true, then we have found an inversion pair, and we print it.
Algorithm
- Initialize two loops, the outer loop (i) from 0 to size - 1 and the inner loop (j) from i + 1 to size - 1.
- For each pair of elements (arr[i], arr[j]), check if arr[i] > arr[j].
- If the condition is true, print the inversion pair (arr[i], arr[j]).
Pseudocode
function printInversionPairs(arr, size):
for i from 0 to size - 1:
for j from i + 1 to size - 1:
if arr[i] > arr[j]:
print (arr[i], arr[j])
end function
Code Solution
-
1) Print Inversions pairs of array of java
2) Print Inversions pairs of array in c++
3) Print Inversions pairs of array in c
4) Print Inversions pairs of array in c#
5) Print Inversions pairs of array in vb.net
6) Print Inversions pairs of array in php
7) Print Inversions pairs of array in node js
8) Print Inversions pairs of array in typescript
9) Print Inversions pairs of array in python
10) Print Inversions pairs of array in ruby
11) Print Inversions pairs of array in scala
12) Print Inversions pairs of array in swift
13) Print Inversions pairs of array in kotlin
14) Print Inversions pairs of array in golang
Time Complexity
- The above algorithm has a time complexity of O(N^2), where N is the number of elements in the array. This is because we use two nested loops to check all pairs of elements in the array.
- As the size of the array increases, the time taken to find inversion pairs grows quadratically.
Resultant Output Explanation
The given program implements the algorithm to find and display all inversion pairs in the given array.
In the provided output, the program displays the inversion pairs in the array [1, 7, 6, 4, 5, 9, 8]. Each pair is printed in the format (x, y), where x is greater than y. The output correctly shows all inversion pairs present in the array.
The output lists the following inversion pairs:
(7, 6)
(7, 4)
(7, 5)
(6, 4)
(6, 5)
(9, 8)
These are the pairs of elements where the element on the left is greater than the element on the right, fulfilling the condition for an inversion pair.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment