Counting cross lines in an array | c ++ program to count cross line in array ; Merges two subarrays of arr [ ] . First subarray is arr [ l . . m ] Second subarray is arr [ m + 1. . r ] ; create temp arrays ; Copy data to temp arrays L [ ] and R [ ] ; i = 0 ; Initial index of first subarray j = 0 ; Initial index of second subarray k = l ; Initial index of merged subarray ; == == == == == == == == == == == == == == == == == == == == == = MAIN PORTION OF CODE == == == == == == == == == == == == == == == == == == == == = add all line which is cross by current element ; Copy the remaining elements of L [ ] , if there are any ; Copy the remaining elements of R [ ] , if there are any ; l is for left index and r is right index of the sub - array of arr to be sorted ; Same as ( l + r ) / 2 , but avoids overflow for large l and h ; Sort first and second halves ; function return count of cross line in an array ; driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void merge ( int arr [ ] , int l , int m , int r , int * count_crossline ) { int i , j , k ; int n1 = m - l + 1 ; int n2 = r - m ; int L [ n1 ] , R [ n2 ] ; for ( i = 0 ; i < n1 ; i ++ ) L [ i ] = arr [ l + i ] ; for ( j = 0 ; j < n2 ; j ++ ) R [ j ] = arr [ m + 1 + j ] ; while ( i < n1 && j < n2 ) { if ( L [ i ] <= R [ j ] ) { arr [ k ] = L [ i ] ; i ++ ; } else { arr [ k ] = R [ j ] ; * count_crossline += ( n1 - i ) ; j ++ ; } k ++ ; } while ( i < n1 ) { arr [ k ] = L [ i ] ; i ++ ; k ++ ; } while ( j < n2 ) { arr [ k ] = R [ j ] ; j ++ ; k ++ ; } } void mergeSort ( int arr [ ] , int l , int r , int * count_crossline ) { if ( l < r ) { int m = l + ( r - l ) / 2 ; mergeSort ( arr , l , m , count_crossline ) ; mergeSort ( arr , m + 1 , r , count_crossline ) ; merge ( arr , l , m , r , count_crossline ) ; } } int countCrossLine ( int arr [ ] , int n ) { int count_crossline = 0 ; mergeSort ( arr , 0 , n - 1 , & count_crossline ) ; return count_crossline ; } int main ( ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countCrossLine ( arr , n ) << endl ; return 0 ; }