Search code examples
pythonalgorithmquicksortmergesort

Is it possible to calculate the number of count inversions using quicksort?


I have already solved the problem using mergesort, now I am thinking is that possible to calculate the number using quicksort? I also coded the quicksort, but I don't know how to calculate. Here is my code:

def Merge_and_Count(AL, AR):
    count=0
    i = 0
    j = 0
    A = []
    for index in range(0, len(AL) + len(AR)):        
        if i<len(AL) and j<len(AR):
            if AL[i] > AR[j]:
                A.append(AR[j])
                j = j + 1
                count = count+len(AL) - i
            else:
                A.append(AL[i])
                i = i + 1
        elif i<len(AL):
            A.append(AL[i])
            i=i+1
        elif j<len(AR):
            A.append(AR[j])
            j=j+1
    return(count,A)

def Sort_and_Count(Arrays):
        if len(Arrays)==1:
            return (0,Arrays)
        list1=Arrays[:len(Arrays) // 2]
        list2=Arrays[len(Arrays) // 2:]
        (LN,list1) = Sort_and_Count(list1)
        (RN,list2) = Sort_and_Count(list2)
        (M,Arrays)= Merge_and_Count(list1,list2)
        return (LN + RN + M,Arrays)

Solution

  • Generally no, because during the partitioning, when you move a value to its correct side of the pivot, you don't know how many of the values you're moving it past are smaller than it and how many are larger. So, as soon as you do that you've lost information about the number of inversions in the original input.