Count Inversions of size three in a given array | A O ( n ^ 2 ) C ++ program to count inversions of size 3 ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getInvCount ( int arr [ ] , int n ) { int invcount = 0 ; for ( int i = 1 ; 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 ; } int main ( ) { int arr [ ] = { 8 , 4 , 2 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Inversion ▁ Count ▁ : ▁ " << getInvCount ( arr , n ) ; return 0 ; }