python - クイックソートを使用してカウント反転の数を計算することは可能ですか?

Question

マージソートを使用して問題を解決しましたが、クイックソートを使用して数値を計算することは可能でしょうか? クイックソートもコーディングしましたが、計算方法がわかりません。これが私のコードです：</p>

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)

Answer 1

通常はいいえ。分割中に値をピボットの正しい側に移動すると、過去に移動している値のうちいくつがそれよりも小さく、いくつが大きいかがわからないためです。したがって、それを行うとすぐに、元の入力の反転数に関する情報が失われます。