Check if an array can be sorted by rearranging odd and even-indexed elements or not
Given an array arr[] of size N, the task is to check if it is possible to sort the array using the following operations:
- Swap(arr[i], arr[j]), if i & 1 = 1 and j & 1 = 1.
- Swap(arr[i], arr[j]), if i & 1 = 0 and j & 1 = 0.
Examples:
Input: arr[] = {3, 5, 1, 2, 6}
Output: Yes
Explanation:
Swap(3, 1) –> {1, 5, 3, 2, 6}
Swap(5, 2) –> {1, 2, 3, 5, 6}Input: arr[] = {3, 1, 5, 2, 6}
Output: No
Naive Approach: The idea is to find the minimum element for the even indexes or odd indexes and swap it from the current element if the index of the current element is even or odd respectively.
- Traverse the array arr[] and perform the following operations:
- If the current index is even, traverse the remaining even indices.
- Find the minimum element present in the even-indexed elements.
- Swap the minimum with the current array element.
- Repeat the above steps for all odd-indexed elements also.
- After completing the above operations, if the array is sorted, then it is possible to sort the array.
- Otherwise, it is not possible to sort the array.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to check if array // can be sorted or not bool isSorted( int arr[], int n) { for ( int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to check if given // array can be sorted or not bool sortPoss( int arr[], int n) { // Traverse the array for ( int i = 0; i < n; i++) { int idx = -1; int minVar = arr[i]; // Traverse remaining elements // at indices separated by 2 int j = i; while (j < n) { // If current element // is the minimum if (arr[j] < minVar) { minVar = arr[j]; idx = j; } j = j + 2; } // If any smaller minimum exists if (idx != -1) { // Swap with current element swap(arr[i], arr[idx]); } } // If array is sorted if (isSorted(arr, n)) return true ; // Otherwise else return false ; } // Driver Code int main() { // Given array int arr[] = { 3, 5, 1, 2, 6 }; int n = sizeof (arr) / sizeof (arr[0]); if (sortPoss(arr, n)) cout << "True" ; else cout << "False" ; return 0; } // This code is contributed by ukasp |
Java
class GFG{ // Function to check if array // can be sorted or not public static boolean isSorted( int arr[], int n) { for ( int i = 0 ; i < n - 1 ; i++) { if (arr[i] > arr[i + 1 ]) return false ; } return true ; } // Function to check if given // array can be sorted or not public static boolean sortPoss( int arr[], int n) { // Traverse the array for ( int i = 0 ; i < n; i++) { int idx = - 1 ; int minVar = arr[i]; // Traverse remaining elements // at indices separated by 2 int j = i; while (j < n) { // If current element // is the minimum if (arr[j] < minVar) { minVar = arr[j]; idx = j; } j = j + 2 ; } // If any smaller minimum exists if (idx != - 1 ) { // Swap with current element int t; t = arr[i]; arr[i] = arr[idx]; arr[idx] = t; } } // If array is sorted if (isSorted(arr, n)) return true ; // Otherwise else return false ; } // Driver Code public static void main(String args[]) { // Given array int arr[] = { 3 , 5 , 1 , 2 , 6 }; int n = arr.length; if (sortPoss(arr, n)) System.out.println( "True" ); else System.out.println( "False" ); } } // This code is contributed by SoumikMondal |
Python3
# Function to check if array # can be sorted or not def isSorted(arr): for i in range ( len (arr) - 1 ): if arr[i]>arr[i + 1 ]: return False return True # Function to check if given # array can be sorted or not def sortPoss(arr): # Traverse the array for i in range ( len (arr)): idx = - 1 minVar = arr[i] # Traverse remaining elements # at indices separated by 2 for j in range (i, len (arr), 2 ): # If current element # is the minimum if arr[j]<minVar: minVar = arr[j] idx = j # If any smaller minimum exists if idx ! = - 1 : # Swap with current element arr[i], arr[idx] = arr[idx], arr[i] # If array is sorted if isSorted(arr): return True # Otherwise else : return False # Driver Code # Given array arr = [ 3 , 5 , 1 , 2 , 6 ] print (sortPoss(arr)) |
C#
using System; class GFG{ // Function to check if array // can be sorted or not public static bool isSorted( int [] arr, int n) { for ( int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to check if given // array can be sorted or not public static bool sortPoss( int [] arr, int n) { // Traverse the array for ( int i = 0; i < n; i++) { int idx = -1; int minVar = arr[i]; // Traverse remaining elements // at indices separated by 2 int j = i; while (j < n) { // If current element // is the minimum if (arr[j] < minVar) { minVar = arr[j]; idx = j; } j = j + 2; } // If any smaller minimum exists if (idx != -1) { // Swap with current element int t; t = arr[i]; arr[i] = arr[idx]; arr[idx] = t; } } // If array is sorted if (isSorted(arr, n)) return true ; // Otherwise else return false ; } // Driver code static public void Main() { // Given array int [] arr = { 3, 5, 1, 2, 6 }; int n = arr.Length; if (sortPoss(arr, n)) Console.WriteLine( "True" ); else Console.WriteLine( "False" ); } } // This code is contributed by offbeat |
Javascript
<script> // Function to check if array // can be sorted or not function isSorted(arr , n) { for (i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to check if given // array can be sorted or not function sortPoss(arr , n) { // Traverse the array for (i = 0; i < n; i++) { var idx = -1; var minVar = arr[i]; // Traverse remaining elements // at indices separated by 2 var j = i; while (j < n) { // If current element // is the minimum if (arr[j] < minVar) { minVar = arr[j]; idx = j; } j = j + 2; } // If any smaller minimum exists if (idx != -1) { // Swap with current element var t; t = arr[i]; arr[i] = arr[idx]; arr[idx] = t; } } // If array is sorted if (isSorted(arr, n)) return true ; // Otherwise else return false ; } // Driver Code // Given array var arr = [ 3, 5, 1, 2, 6 ]; var n = arr.length; if (sortPoss(arr, n)) document.write( "True" ); else document.write( "False" ); // This code contributed by umadevi9616 </script> |
True
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to check if utilize the fact that we can arrange all the even indexed and odd indexed elements the way we want to use the swap operations.
- Initialize an array, say dupArr[], to store the contents of the given array.
- Sort the array dupArr[].
- Check if all even-indexed elements in the original array are the same as the even-indexed elements in dupArr[].
- If found to be true, then sorting is possible. Otherwise, sorting is not possible.
Below is the implementation of the above approach:
C++
// C++ implementation of the // above approach #include<bits/stdc++.h> using namespace std; // Function to check if array can // be sorted by given operations bool isEqual(vector< int >&A,vector< int >&B){ if (A.size() != B.size()) return false ; for ( int i = 0; i < A.size(); i++){ if (A[i] != B[i]) return false ; } return true ; } bool sortPoss(vector< int >arr){ // Copy contents // of the array vector< int >dupArr(arr.begin(),arr.end()); // Sort the duplicate array sort(dupArr.begin(),dupArr.end()); vector< int >evenOrg; vector< int >evenSort; // Traverse the array for ( int i=0;i<arr.size();i+=2){ // Append even-indexed elements // of the original array evenOrg.push_back(arr[i]); // Append even-indexed elements // of the duplicate array evenSort.push_back(dupArr[i]); } // Sort the even-indexed elements sort(evenOrg.begin(),evenOrg.end()); sort(evenSort.begin(),evenSort.end()); // Return true if even-indexed // elements are identical return isEqual(evenOrg,evenSort); } // Driver Code int main(){ // Given array vector< int >arr = {3, 5, 1, 2, 6}; cout << sortPoss(arr) << endl; } // This code is contributed by shinjanpatra. |
Java
// Java implementation of the // above approach import java.io.*; import java.util.*; import java.util.ArrayList; class GFG { // Function to check if array can // be sorted by given operations public static boolean isEqual(ArrayList<Integer> A,ArrayList<Integer> B){ if (A.size() != B.size()) return false ; for ( int i = 0 ; i < A.size(); i++){ if (A.get(i) != B.get(i)) return false ; } return true ; } public static boolean sortPoss( int [] arr){ // Copy contents // of the array ArrayList<Integer> dupArr = new ArrayList<Integer>(); for ( int i = 0 ; i < arr.length; i++) { dupArr.add(arr[i]); } // Sort the duplicate array Collections.sort(dupArr); ArrayList<Integer> evenOrg = new ArrayList<Integer>(); ArrayList<Integer> evenSort = new ArrayList<Integer>(); // Traverse the array for ( int i = 0 ; i < arr.length; i += 2 ){ // Append even-indexed elements // of the original array evenOrg.add(arr[i]); // Append even-indexed elements // of the duplicate array evenSort.add(dupArr.get(i)); } // Sort the even-indexed elements Collections.sort(evenOrg); Collections.sort(evenSort); // Return true if even-indexed // elements are identical return isEqual(evenOrg,evenSort); } // Driver Code public static void main (String[] args) { // Given array int [] arr = { 3 , 5 , 1 , 2 , 6 }; System.out.println(sortPoss(arr)); } } // This code is contributed by Aman Kumar. |
Python3
# Python Program to implement # the above approach # Function to check if array can # be sorted by given operations def sortPoss(arr): # Copy contents # of the array dupArr = list (arr) # Sort the duplicate array dupArr.sort() evenOrg = [] evenSort = [] # Traverse the array for i in range ( 0 , len (arr), 2 ): # Append even-indexed elements # of the original array evenOrg.append(arr[i]) # Append even-indexed elements # of the duplicate array evenSort.append(dupArr[i]) # Sort the even-indexed elements evenOrg.sort() evenSort.sort() # Return true if even-indexed # elements are identical return evenOrg = = evenSort # Driver Code # Given array arr = [ 3 , 5 , 1 , 2 , 6 ] print (sortPoss(arr)) |
C#
// C# code to implement the approach using System; using System.Linq; using System.Collections.Generic; class GFG { // Function to check if array can // be sorted by given operations public static bool isEqual(List< int > A,List< int > B){ if (A.Count != B.Count) return false ; for ( int i = 0; i < A.Count; i++){ if (A[i] != B[i]) return false ; } return true ; } public static bool sortPoss( int [] arr){ // Copy contents of the array List< int > dupArr = arr.ToList(); // Sort the duplicate array dupArr.Sort(); List< int > evenOrg = new List< int >(); List< int > evenSort = new List< int >(); // Traverse the array for ( int i = 0; i < arr.Length; i += 2){ // Append even-indexed elements // of the original array evenOrg.Add(arr[i]); // Append even-indexed elements // of the duplicate array evenSort.Add(dupArr[i]); } // Sort the even-indexed elements evenOrg.Sort(); evenSort.Sort(); // Return true if even-indexed // elements are identical return isEqual(evenOrg,evenSort); } // Driver Code public static void Main( string [] args) { // Given array int [] arr = {3, 5, 1, 2, 6}; Console.WriteLine(sortPoss(arr)); } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if array can // be sorted by given operations function isEqual(A,B){ if (A.length != B.length) return false ; for (let i = 0; i < A.length; i++){ if (A[i] != B[i]) return false ; } return true ; } function sortPoss(arr){ // Copy contents // of the array let dupArr = arr.slice(); // Sort the duplicate array dupArr.sort() let evenOrg = [] let evenSort = [] // Traverse the array for (let i=0;i<arr.length;i+=2){ // Append even-indexed elements // of the original array evenOrg.push(arr[i]) // Append even-indexed elements // of the duplicate array evenSort.push(dupArr[i]) } // Sort the even-indexed elements evenOrg.sort() evenSort.sort() // Return true if even-indexed // elements are identical return isEqual(evenOrg,evenSort); } // Driver Code // Given array let arr = [3, 5, 1, 2, 6] document.write(sortPoss(arr), "</br>" ) // This code is contributed by shinjanpatra. </script> |
True
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Contact Us