Sort an almost sorted array where only two elements are swapped | C ++ program to sort using one swap ; This function sorts an array that can be sorted by single swap ; Traverse the given array from rightmost side ; Check if arr [ i ] is not in order ; Find the other element to be swapped with arr [ i ] ; Swap the pair ; A utility function to print an array of size n ; Driver program to test insertion sort
#include <iostream> NEW_LINE #include <algorithm> NEW_LINE using namespace std ; void sortByOneSwap ( int arr [ ] , int n ) { for ( int i = n - 1 ; i > 0 ; i -- ) { if ( arr [ i ] < arr [ i - 1 ] ) { int j = i - 1 ; while ( j >= 0 && arr [ i ] < arr [ j ] ) j -- ; swap ( arr [ i ] , arr [ j + 1 ] ) ; break ; } } } void printArray ( int arr [ ] , int n ) { int i ; for ( i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; cout << endl ; } int main ( ) { int arr [ ] = { 10 , 30 , 20 , 40 , 50 , 60 , 70 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Given ▁ array ▁ is ▁ STRNEWLINE " ; printArray ( arr , n ) ; sortByOneSwap ( arr , n ) ; cout << " Sorted ▁ array ▁ is ▁ STRNEWLINE " ; printArray ( arr , n ) ; return 0 ; }