Count Inversions of size three in a given array | A O ( n ^ 2 ) Java program to count inversions of size 3 ; returns count of inversion 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
class Inversion { int getInvCount ( int arr [ ] , int n ) { int invcount = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { int small = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) if ( arr [ i ] > arr [ j ] ) small ++ ; int great = 0 ; for ( int j = i - 1 ; j >= 0 ; j -- ) if ( arr [ i ] < arr [ j ] ) great ++ ; invcount += great * small ; } return invcount ; } public static void main ( String args [ ] ) { Inversion inversion = new Inversion ( ) ; int arr [ ] = new int [ ] { 8 , 4 , 2 , 1 } ; int n = arr . length ; System . out . print ( " Inversion ▁ count ▁ : ▁ " + inversion . getInvCount ( arr , n ) ) ; } }