Counting Inversion in Python
Counting Inversion in Python
On this page we will learn to create program for counting inversion in Python Programing language for a given array.
Example : –
- Input: A = [6, 3, 5, 2, 7]
- Output: 5
- Explanation: The five pairs of inversions are – (6, 3) , (6, 5), (6, 2), (3, 2), (5, 2)
Did you know?
Two elements a[i] and a[j] form an inversion only if a[i] > a[j] and i < j.
- Inversion count of a number means how close the array is to be sorted
- If the array is already sorted the inversion count of the array will be zero
- If the array is sorted in reverse order inversion count will be maximum
Algorithm
- Initialize a variable ans assign 0
- Iterate using for loop from 0 to length of array using variable i
- Run a nested for loop from i+1 to length of array using variable j
- If element at jth position is smaller then element at ith position in array then increment the value of ans by 1
Python Code
Run
def inversion(arr):
ans = 0
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[j] < arr[i]:
ans += 1
return ans
array = [6, 3, 5, 2, 7]
print("There are", inversion(array), "possible inversion")
Python Code
There are 5 possible inversion
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
For similar Questions click on given button.
Login/Signup to comment
a= [6, 3, 5, 2, 7]
s=0
for i in range(len(a)):
for j in range(len(a)):
if a[i]>a[j] and i<j:
s+=1
print((a[i],a[j]),end=" \n")
print(s)