Check if array can be sorted with one swap | A linear CPP program to check if array becomes sorted after one swap ; Find counts and positions of elements that are out of order . ; If there are more than two elements are out of order . ; If all elements are sorted already ; Cases like { 1 , 5 , 3 , 4 , 2 } We swap 5 and 2. ; Cases like { 1 , 2 , 4 , 3 , 5 } ; Now check if array becomes sorted for cases like { 4 , 1 , 2 , 3 } ; Driver Program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int checkSorted ( int n , int arr [ ] ) { int first = 0 , second = 0 ; int count = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] < arr [ i - 1 ] ) { count ++ ; if ( first == 0 ) first = i ; else second = i ; } } if ( count > 2 ) return false ; if ( count == 0 ) return true ; if ( count == 2 ) swap ( arr [ first - 1 ] , arr [ second ] ) ; else if ( count == 1 ) swap ( arr [ first - 1 ] , arr [ first ] ) ; for ( int i = 1 ; i < n ; i ++ ) if ( arr [ i ] < arr [ i - 1 ] ) return false ; return true ; } int main ( ) { int arr [ ] = { 1 , 4 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( checkSorted ( n , arr ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }