Skip to main content

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

  1. Initialize two loops, the outer loop (i) from 0 to size - 1 and the inner loop (j) from i + 1 to size - 1.
  2. For each pair of elements (arr[i], arr[j]), check if arr[i] > arr[j].
  3. 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

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.





Comment

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