Sort an array with swapping only with a special element is allowed | CPP program to sort an array by moving one space around . ; n is total number of elements . index is index of 999 or space . k is number of elements yet to be sorted . ; print the sorted array when loop reaches the base case ; else if k > 0 and space is at 0 th index swap each number with space and store index at second last index ; if space is neither start of array nor last element of array and element before it greater than / the element next to space ; first swap space and element next to space in case of { 3 , 999 , 2 } make it { 3 , 2 , 999 } ; than swap space and greater element convert { 3 , 2 , 999 } to { 999 , 2 , 3 } ; Wrapper over sortRec . ; Find index of space ( or 999 ) ; Invalid input ; driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; void sortRec ( int arr [ ] , int index , int k , int n ) { if ( k == 0 ) { for ( int i = 1 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; cout << 999 ; return ; } else if ( k > 0 && index == 0 ) { index = n - 2 ; for ( int i = 1 ; i <= index ; i ++ ) { arr [ i - 1 ] = arr [ i ] ; } arr [ index ] = 999 ; } if ( index - 1 >= 0 && index + 1 < n && arr [ index - 1 ] > arr [ index + 1 ] ) { swap ( arr [ index ] , arr [ index + 1 ] ) ; swap ( arr [ index - 1 ] , arr [ index + 1 ] ) ; } else swap ( arr [ index ] , arr [ index - 1 ] ) ; sortRec ( arr , index - 1 , k - 1 , n ) ; } void sort ( int arr [ ] , int n ) { int index = -1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] == 999 ) { index = i ; break ; } } if ( index == -1 ) return ; sortRec ( arr , index , n , n ) ; } int main ( ) { int arr [ ] = { 3 , 2 , 999 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; sort ( arr , n ) ; return 0 ; }