Short Problem Definition:
Compute number of inversion in an array.
Link
Complexity:
expected worst-case time complexity is O(N\*log(N))
expected worst-case space complexity is O(N)
Execution:
Any sorting algorithm with a NlogN runtime will do the trick. It is important to count all (remaining) bigger elements on the left side. Do not forget to check for the maximal return value!
Solution:
MAX_NR = 1000000000
def mergeSort(alist):
inversion_count = 0
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
inversion_count += mergeSort(lefthalf)
if (inversion_count > MAX_NR):
raise
inversion_count += mergeSort(righthalf)
if (inversion_count > MAX_NR):
raise
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<=righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
inversion_count += len(lefthalf)-i
if (inversion_count > MAX_NR):
raise
k=k+1
while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
return inversion_count
def solution(A):
try:
return mergeSort(A)
except:
return -1