Count Inversions of size three in a given array | Returns count of inversions of size 3 ; Initialize result ; Count all smaller elements on right of arr [ i ] ; Count all greater elements on left of arr [ i ] ; Update inversion count by adding all inversions that have arr [ i ] as middle of three elements ; Driver program to test above function
def getInvCount ( arr , n ) : NEW_LINE INDENT invcount = 0 NEW_LINE for i in range ( 1 , n - 1 ) : NEW_LINE INDENT small = 0 NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] ) : NEW_LINE INDENT small += 1 NEW_LINE DEDENT DEDENT great = 0 ; NEW_LINE for j in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] < arr [ j ] ) : NEW_LINE INDENT great += 1 NEW_LINE DEDENT DEDENT invcount += great * small NEW_LINE DEDENT return invcount NEW_LINE DEDENT arr = [ 8 , 4 , 2 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Inversion ▁ Count ▁ : " , getInvCount ( arr , n ) ) NEW_LINE