Sort an array by swapping elements of different type specified by another array | C ++ program to check if it is possible to sort the array in non - decreasing order by swapping elements of different types ; Function to check if it is possible to sort the array in non - decreasing order by swapping elements of different types ; Consider the array to be already sorted ; checking if array is already sorted ; Check for a pair which is in decreasing order ; Count the frequency of each type of element ; type0 stores count of elements of type 0 ; type1 stores count of elements of type 1 ; Return true if array is already sorted ; Return false if all elements are of same type and array is unsorted ; Possible for all other cases ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool sorting_possible ( int a [ ] , int b [ ] , int n ) { bool sorted = true ; int type1 = 0 , type0 = 0 , i ; for ( i = 1 ; i < n ; i ++ ) { if ( a [ i ] < a [ i - 1 ] ) { sorted = false ; break ; } } for ( i = 0 ; i < n ; i ++ ) { if ( b [ i ] == 0 ) type0 ++ ; else type1 ++ ; } if ( sorted ) return true ; else if ( type1 == n type0 == n ) return false ; else return true ; } int main ( ) { int a [ ] = { 15 , 1 , 2 , 17 , 6 } ; int b [ ] = { 1 , 1 , 0 , 1 , 1 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; bool res = sorting_possible ( a , b , n ) ; if ( res ) cout << " Yes " ; else cout << " No " ; }