inversions in array in c code example
Example: counting inversions
'''for counting pairs the best algo has time complexty O(n*log(n))'''
''' for collecting such pairs the best algo. has time complexity O(n*n)'''
PAIRS=0
def merge(left,right):
global PAIRS
length_1,length_2=len(left),len(right)
index1,index2=0,0
ans=[]
for i in range(length_1+length_2):
if index1==length_1:
ans.append(right[index2])
index2+=1
elif index2==length_2:
ans.append(left[index1])
index1+=1
elif left[index1]<right[index2]:
ans.append(left[index1])
index1+=1
else:
ans.append(right[index2])
PAIRS+=length_1-index1
index2+=1
return ans
def find_all_pairs(lst):
pairs=[]
for i in range(len(lst)):
for j in range(i,len(lst)):
if lst[i]>lst[j]:pairs.append((lst[j],lst[i]))
return pairs
def memsort(lst):
global PAIRS
if len(lst)<3:
if len(lst)==2:
if lst[0]>lst[1]:
lst[1],lst[0]=lst[0],lst[1]
PAIRS+=1
else:
mid=len(lst)//2
left=lst[:mid]
right=lst[mid:]
left=memsort(left)
right=memsort(right)
lst=merge(left,right)
return lst
if __name__=='__main__':
a=[int(i) for i in input('Enter the list of Numbers: ').split()]
print(find_all_pairs(a))
memsort(a)
print(PAIRS)