Sort an Array by decreasing and increasing elements with adjacent swaps
Given an array arr[] of size N. The task is to make an array in increasing order where you are allowed (any number of times) to swap adjacent elements and decrease the value with a smaller index by 1 and increase the value of a greater index by 1. Output “Yes” if it is possible to arrange the array in increasing order otherwise, “No”.
Input: N = 4, arr[] = 6 2 8 9
Output: Yes
Explanation: Swap 1st and Second element, New array is [3, 5, 8, 9] now it is sorted.Input: N = 3, arr[] = {20, 1, 18}
Output: No
Explanation: We cannot obtain a sorted array by swapping adjacent elements by increasing and decreasing their values.
Approach: This can be solved with the following idea:
Checking adjacent elements, if adjacent elements have a difference of 1, then it is not possible to sort them. If after swapping again the difference between 1 return “No“.
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> using namespace std; // Function to sort an array using adjacent // swaps with value decrease / increase void SortingArrayswithAdjacentSwaps( int n, vector< int >& a) { // Initialize flag variable to indicate // whether a sorted array exists or not bool possible = true ; // Iterate through the array for ( int i = 0; i < n - 1; i++) { // Check if the current element is // greater than the next element if (a[i] > a[i + 1]) { // Calculate the difference // between the current and // next element int diff = a[i] - a[i + 1]; // If the difference is 1, // it is not possible to // sort the array if (diff == 1) { possible = false ; break ; } // Swap the adjacent elements, // with value decrease / increase int temp1 = a[i] - 1; int temp2 = a[i + 1] + 1; a[i] = temp2; a[i + 1] = temp1; // Check if the current element // is greater than the previous // element, After swapping there // may be a chance of an unsorted array. if (i >= 1 && a[i - 1] > a[i]) { possible = false ; break ; } } } if (possible) cout << "YES" << endl; else cout << "NO" << endl; } // Driver code int main() { int n = 4; vector< int > a = {6, 2, 8, 9}; // Function call SortingArrayswithAdjacentSwaps(n, a); return 0; } |
Java
//Python code for the above approach: import java.util.ArrayList; import java.util.List; public class SortingArraysWithAdjacentSwaps { // Function to sort an array using adjacent // swaps with value decrease / increase public static void sortArraysWithAdjacentSwaps( int n, List<Integer> a) { // Initialize flag variable to indicate // whether a sorted array exists or not boolean possible = true ; // Iterate through the array for ( int i = 0 ; i < n - 1 ; i++) { // Check if the current element is // greater than the next element if (a.get(i) > a.get(i + 1 )) { // Calculate the difference // between the current and // next element int diff = a.get(i) - a.get(i + 1 ); // If the difference is 1, // it is not possible to // sort the array if (diff == 1 ) { possible = false ; break ; } // Swap the adjacent elements, // with value decrease / increase int temp1 = a.get(i) - 1 ; int temp2 = a.get(i + 1 ) + 1 ; a.set(i, temp2); a.set(i + 1 , temp1); // Check if the current element // is greater than the previous // element, After swapping there // may be a chance of an unsorted array. if (i >= 1 && a.get(i - 1 ) > a.get(i)) { possible = false ; break ; } } } if (possible) System.out.println( "YES" ); else System.out.println( "NO" ); } // Driver code public static void main(String[] args) { int n = 4 ; List<Integer> a = new ArrayList<>(); a.add( 6 ); a.add( 2 ); a.add( 8 ); a.add( 9 ); // Function call sortArraysWithAdjacentSwaps(n, a); } } |
Python3
# Python code for the above approach: # Function to sort an array using adjacent # swaps with value decrease / increase def SortingArrayswithAdjacentSwaps(n, a): # Initialize flag variable to indicate # whether a sorted array exists or not possible = True # Iterate through the array for i in range (n - 1 ): # Check if the current element is # greater than the next element if a[i] > a[i + 1 ]: # Calculate the difference # between the current and # next element diff = a[i] - a[i + 1 ] # If the difference is 1, # it is not possible to # sort the array if diff = = 1 : possible = False break # Swap the adjacent elements, # with value decrease / increase temp1 = a[i] - 1 temp2 = a[i + 1 ] + 1 a[i] = temp2 a[i + 1 ] = temp1 # Check if the current element # is greater than the previous # element, After swapping there # may be chance of unsorted array. if i > = 1 and a[i - 1 ] > a[i]: possible = False break if possible: print ( "YES" ) else : print ( "NO" ) # Driver code n = 4 a = [ 6 , 2 , 8 , 9 ] # Function call SortingArrayswithAdjacentSwaps(n, a) |
C#
// C# code for the above approach using System; using System.Collections.Generic; public class GFG { // Function to sort an array using adjacent // swaps with value decrease / increase static void SortingArrayswithAdjacentSwaps( int n, List< int > a) { // Initialize flag variable to indicate // whether a sorted array exists or not bool possible = true ; // Iterate through the array for ( int i = 0; i < n - 1; i++) { // Check if the current element is // greater than the next element if (a[i] > a[i + 1]) { // Calculate the difference // between the current and // next element int diff = a[i] - a[i + 1]; // If the difference is 1, // it is not possible to // sort the array if (diff == 1) { possible = false ; break ; } // Swap the adjacent elements, // with value decrease / increase int temp1 = a[i] - 1; int temp2 = a[i + 1] + 1; a[i] = temp2; a[i + 1] = temp1; // Check if the current element // is greater than the previous // element, After swapping there // may be a chance of an unsorted array. if (i >= 1 && a[i - 1] > a[i]) { possible = false ; break ; } } } if (possible) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } // Driver code static void Main( string [] args) { int n = 4; List< int > a = new List< int >{ 6, 2, 8, 9 }; // Function call SortingArrayswithAdjacentSwaps(n, a); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Javascript code for the above approach: // Function to sort an array using adjacent swaps with value decrease / increase function sortArraysWithAdjacentSwaps(n, a) { // Initialize flag variable to indicate whether a sorted array exists or not let possible = true ; // Iterate through the array for (let i = 0; i < n - 1; i++) { // Check if the current element is greater than the next element if (a[i] > a[i + 1]) { // Calculate the difference between the current and next element let diff = a[i] - a[i + 1]; // If the difference is 1, it is not possible to sort the array if (diff === 1) { possible = false ; break ; } // Swap the adjacent elements, with value decrease / increase let temp1 = a[i] - 1; let temp2 = a[i + 1] + 1; a[i] = temp2; a[i + 1] = temp1; // Check if the current element is greater than the previous element, // After swapping there may be a chance of an unsorted array. if (i >= 1 && a[i - 1] > a[i]) { possible = false ; break ; } } } // Print the result if (possible) console.log( "YES" ); else console.log( "NO" ); } // Driver code const n = 4; const a = [6, 2, 8, 9]; // Function call sortArraysWithAdjacentSwaps(n, a); |
YES
Time Complexity: O(N)
Auxiliary Space: O(1)