Number of steps to sort the array by changing order of three elements in each step
Given an array arr[] of size N consisting of unique elements in the range [0, N-1], the task is to find K which is the number of steps required to sort the given array by selecting three distinct elements and rearranging them. And also, print the indices selected in those K steps in K lines.
For example, in the array {5, 4, 3, 2, 1, 0}, one possible way to sort the given array by selecting three distinct elements is to select the numbers {2, 1, 0} and sort them as {0, 1, 2} thereby making the array {5, 4, 3, 0, 1, 2}. Similarly, the remaining operations are performed and the indices selected ({3, 4, 5} in the above case) are printed in separate lines.
Examples:
Input: arr[] = {0, 5, 4, 3, 2, 1}
Output:
2
1 2 5
2 5 4
Explanation:
The above array can be sorted in 2 steps:
Step I: We change the order of elements at indices 1, 2, 5 then the array becomes {0, 1, 5, 3, 2, 4}.
Step II: We again change the order of elements at the indices 2, 5, 4 then the array becomes {0, 1, 2, 3, 4, 5} which is sorted.
Input: arr[] = {0, 3, 1, 6, 5, 2, 4}
Output: -1
Explanation:
The above array cannot be sorted in any number of steps.
Suppose we choose indices 1, 3, 2 then the array becomes {0, 1, 6, 3, 5, 2, 4}
After that, we choose indices 2, 6, 4 then the array becomes {0, 1, 5, 3, 4, 2, 6}.
Now only two elements are left unsorted so we cannot choose 3 elements so the above array cannot be sorted. We can try with any order of indices and we will always be left with 2 elements unsorted.
Approach: The idea is to first count the elements which are not sorted and insert them in an unordered set. If count is 0 then we don’t need any number of steps for sorting the array so we print 0 and exit. Else, we first erase all the elements from the set for which i = A[A[i]] then we perform the following operation till the set becomes empty:
- We select all the possible combination of indices(if available) such that minimum two elements will get sorted.
- Now, change the order of the elements and erase them from the set if i = A[i].
- Then, we are left with only those elements such that i = A[A[i]] and the count of those must be a multiple of 4 otherwise it is not possible to sort the elements.
- Then, we choose any two pair and perform changing the order of elements two times. Then all the four chosen elements will get sorted.
- We store all the indices which are involved in the changing of orders of elements in a vector and print it as the answer.
Let’s understand the above approach with an example. Let the array arr[] = {0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11}. Then:
- Initially, the set will contain all the 12 elements and there are no elements such that i = A[A[i]].
- Now, {11, 5, 7} are chosen and the order of the elements are changed. Then, arr[] = {0, 8, 9, 10, 1, 5, 12, 7, 3, 2, 6, 4, 11}.
- Now, {11, 4, 1} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 10, 4, 5, 12, 7, 3, 2, 6, 8, 11}.
- Now, {11, 8, 3} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 3, 4, 5, 12, 7, 8, 2, 6, 10, 11}.
- Now, {11, 10, 6} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 3, 4, 5, 6, 7, 8, 2, 10, 12, 11}.
- After the above step, we are left with two pairs of unsorted elements such that i = A[A[i]].
- Finally, {2, 11, 9} and {11, 9, 5} are chosen and reordered. Then, arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} which is sorted.
Below is the implementation of the above approach:
CPP
// C++ program to sort the array // by changing the order of // three elements #include <bits/stdc++.h> using namespace std; // Function to change the order of // the elements having a temporary // vector and the required indices // as the arguments void cngorder(vector< int >& v, int i, int j, int k) { int temp = v[k]; v[k] = v[j]; v[j] = v[i]; v[i] = temp; } // Function to sort the elements having // the given array and its size. void sortbyorder3(vector< int >& A, int n) { // Flag to check whether the sorting // is possible or not bool flag = 0; int count = 0; // Set that will contains unsorted // elements unordered_set< int > s; // Iterating through the elements for ( int i = 0; i < n; i++) { // Inserting the required elements // in the set if (i != A[i]) count++, s.insert(i); } // When the given array is // already sorted if (count == 0) cout << "0" << endl; else { // Vector that will contain // the answer vector<vector< int > > ans; // Temporary vector to store // the indices vector< int > vv; int x, y, z; count = 0; // Loop that will execute till the // set becomes empty while (!s.empty()) { auto it = s.begin(); int i = *it; // Check for the condition if (i == A[A[i]]) { s.erase(i); s.erase(A[i]); continue ; } // Case when the minimum two // elements will get sorted else { x = A[i], y = A[A[i]], z = A[A[A[i]]]; vv.push_back(x), vv.push_back(y), vv.push_back(z); // Changing the order of elements cngorder(A, x, y, z); // Pushing the indices to the // answer vector ans.push_back(vv); // If the third element also // gets sorted if (vv[0] == A[vv[0]]) s.erase(vv[0]); // Erasing the two sorted elements // from the set s.erase(vv[1]), s.erase(vv[2]); vv.clear(); } } count = 0; // The count of the remaining // unsorted elements for ( int i = 0; i < n; i++) { if (i != A[i]) count++; } // If the count of the left // unsorted elements is not // a multiple of 4, then // sorting is not possible if (count % 4 != 0) flag = 1; // Only the elements such that // i = A[A[i]] are left // for sorting else { // Indices of any one element // from the two pairs that // will be sorted in 2 steps int i1 = -1, i2 = -1; for ( int i = 0; i < n; i++) { // Index of any element of // the pair if (A[i] != i && i1 == -1) { i1 = i; } // When we find the second // pair and the index of // any one element is stored else if (A[i] != i && i1 != -1 && i2 == -1) { if (i1 == A[i]) continue ; else i2 = i; } // When we got both the pair // of elements if (i1 != -1 && i2 != -1) { // Remaining two indices // of the elements int i3 = A[i1], i4 = A[i2]; // The first order of indices vv.push_back(i1), vv.push_back(i2), vv.push_back(A[i1]); // Pushing the indices to the // answer vector ans.push_back(vv); vv.clear(); // The second order of indices vv.push_back(i2), vv.push_back(A[i1]), vv.push_back(A[i2]); // Pushing the indices to the // answer vector ans.push_back(vv); vv.clear(); // Changing the order of the // first combination of // the indices cngorder(A, i1, i2, i3); // Changing the order of the // second combination of // the indices after which all // the 4 elements will be sorted cngorder(A, i2, i3, i4); i1 = -1, i2 = -1; } } } // If the flag value is 1 // the sorting is not possible if (flag == 1) cout << "-1" << endl; else { // Printing the required number // of steps cout << ans.size() << endl; // Printing the indices involved // in the shifting for ( int i = 0; i < ans.size(); i++) { cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << endl; } } } } // Driver code int main() { int n; vector< int > A{ 0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11 }; n = A.size(); // Calling the sorting function sortbyorder3(A, n); return 0; } |
Java
// java program to sort the array // by changing the order of // three elements import java.util.*; class Main { // Function to change the order of // the elements having a temporary // vector and the required indices // as the arguments static void cngorder(List<Integer> v, int i, int j, int k) { int temp = v.get(k); v.set(k, v.get(j)); v.set(j, v.get(i)); v.set(i, temp); } // Function to sort the elements having // the given array and its size. static void sortbyorder3(List<Integer> A, int n) { // Flag to check whether the sorting // is possible or not boolean flag = false ; int count = 0 ; // Set that will contains unsorted // elements HashSet<Integer> s = new HashSet<>(); // Iterating through the elements for ( int i = 0 ; i < n; i++) { // Inserting the required elements // in the set if (i != A.get(i)) { count++; s.add(i); } } // When the given array is // already sorted if (count == 0 ) { System.out.println( "0" ); } else { // Vector that will contain // the answer List<List<Integer>> ans = new ArrayList<>(); // Temporary vector to store // the indices List<Integer> vv = new ArrayList<>(); int x, y, z; count = 0 ; // Loop that will execute till the // set becomes empty while (!s.isEmpty()) { Iterator<Integer> it = s.iterator(); // Check for the condition int i = it.next(); if (i == A.get(A.get(i))) { s.remove(i); s.remove(A.get(i)); continue ; } // Case when the minimum two else { x = A.get(i); y = A.get(A.get(i)); z = A.get(A.get(A.get(i))); vv.add(x); vv.add(y); vv.add(z); // Changing the order of elements cngorder(A, x, y, z); // Pushing the indices to the // answer vector ans.add( new ArrayList<>(vv)); // If the third element also // gets sorted if (vv.get( 0 ).equals(A.get(vv.get( 0 )))){ s.remove(vv.get( 0 )); } // Erasing the two sorted elements // from the set s.remove(vv.get( 1 )); s.remove(vv.get( 2 )); vv.clear(); } } count = 0 ; // The count of the remaining // unsorted elements for ( int i = 0 ; i < n; i++) { if (i != A.get(i)) { count++; } } // If the count of the left // unsorted elements is not // a multiple of 4, then // sorting is not possible if (count % 4 != 0 ) { flag = true ; } // Only the elements such that // i = A[A[i]] are left // for sorting else { // Indices of any one element // from the two pairs that // will be sorted in 2 steps int i1 = - 1 , i2 = - 1 ; for ( int i = 0 ; i < n; i++) { // Index of any element of // the pair if (!A.get(i).equals(i) && i1 == - 1 ) { i1 = i; } // When we find the second // pair and the index of // any one element is stored else if (!A.get(i).equals(i) && i1 != - 1 && i2 == - 1 ) { if (i1 == A.get(i)) continue ; else i2 = i; } if (i1 != - 1 && i2 != - 1 ) { // Remaining two indices // of the elements int i3 = A.get(i1), i4 = A.get(i2); // The first order of indices vv.add(i1); vv.add(i2); vv.add(A.get(i1)); // Pushing the indices to the // answer vector ans.add( new ArrayList<>(vv)); vv.clear(); // The second order of indices vv.add(i2); vv.add(A.get(i1)); vv.add(A.get(i2)); // Pushing the indices to the // answer vector ans.add( new ArrayList<>(vv)); vv.clear(); // Changing the order of the // first combination of // the indices cngorder(A, i1, i2, i3); // Changing the order of the // second combination of // the indices after which all // the 4 elements will be sorted cngorder(A, i2, i3, i4); i1 = - 1 ; i2 = - 1 ; } } } // If the flag value is 1 // the sorting is not possible if (flag) { System.out.println( "-1" ); } else { // Printing the required number // of steps System.out.println(ans.size()); // Printing the indices involved // in the shifting for ( int i = 0 ; i < ans.size(); i++) { System.out.println(ans.get(i).get( 0 ) + " " + ans.get(i).get( 1 ) + " " + ans.get(i).get( 2 )); } } } } // Driver code public static void main(String[] args) { List<Integer> A = new ArrayList<>(Arrays.asList( 0 , 8 , 9 , 10 , 1 , 7 , 12 , 4 , 3 , 2 , 6 , 5 , 11 )); int n = A.size(); sortbyorder3(A, n); } } //This code is contributed by shivregkec |
Python3
def cngorder(arr, i, j, k): """ Function to change the order of elements """ temp = arr[k] arr[k] = arr[j] arr[j] = arr[i] arr[i] = temp def sortbyorder3(A, n): """ Function to sort the array by changing the order of three elements """ # Flag to check whether the sorting is possible or not flag = 0 count = 0 # Set that will contain unsorted elements s = set () # Iterating through the elements for i in range (n): # Inserting the required elements in the set if i ! = A[i]: count + = 1 s.add(i) # When the given array is already sorted if count = = 0 : print ( "0" ) else : # Vector that will contain the answer ans = [] # Temporary list to store the indices vv = [] x, y, z = 0 , 0 , 0 count = 0 # Loop that will execute till the set becomes empty while s: i = next ( iter (s)) # Check for the condition if i = = A[A[i]]: s.remove(i) s.remove(A[i]) continue else : x, y, z = A[i], A[A[i]], A[A[A[i]]] vv.extend([x, y, z]) # Changing the order of elements cngorder(A, x, y, z) # Pushing the indices to the answer list ans.append( list (vv)) # If the third element also gets sorted if vv[ 0 ] = = A[vv[ 0 ]]: s.remove(vv[ 0 ]) # Erasing the two sorted elements from the set s.remove(vv[ 1 ]) s.remove(vv[ 2 ]) vv.clear() count = 0 # The count of the remaining unsorted elements for i in range (n): if i ! = A[i]: count + = 1 # If the count of the left unsorted elements is not a multiple of 4, then sorting is not possible if count % 4 ! = 0 : flag = 1 else : i1, i2 = - 1 , - 1 for i in range (n): if A[i] ! = i and i1 = = - 1 : i1 = i elif A[i] ! = i and i1 ! = - 1 and i2 = = - 1 : if i1 = = A[i]: continue else : i2 = i if i1 ! = - 1 and i2 ! = - 1 : i3, i4 = A[i1], A[i2] # The first order of indices vv.extend([i1, i2, A[i1]]) # Pushing the indices to the answer list ans.append( list (vv)) vv.clear() # The second order of indices vv.extend([i2, A[i1], A[i2]]) # Pushing the indices to the answer list ans.append( list (vv)) vv.clear() # Changing the order of the first combination of the indices cngorder(A, i1, i2, i3) # Changing the order of the second combination of the indices after which all the 4 elements will be sorted cngorder(A, i2, i3, i4) i1, i2 = - 1 , - 1 # If the flag value is 1, the sorting is not possible if flag = = 1 : print ( "-1" ) else : # Printing the required number of steps print ( len (ans)) # Printing the indices involved in the shifting for a in ans: print ( * a) # Driver code if __name__ = = "__main__" : A = [ 0 , 8 , 9 , 10 , 1 , 7 , 12 , 4 , 3 , 2 , 6 , 5 , 11 ] n = len (A) # Calling the sorting function sortbyorder3(A, n) |
C#
// C# program to sort the array // by changing the order of // three elements using System; using System.Collections.Generic; class GFG { // Function to change the order of // the elements having a temporary // vector and the required indices // as the arguments static void cngorder(List< int > v, int i, int j, int k) { int temp = v[k]; v[k] = v[j]; v[j] = v[i]; v[i] = temp; } // Function to sort the elements having // the given array and its size. static void sortbyorder3(List< int > A, int n) { // Flag to check whether the sorting // is possible or not bool flag = false ; int count = 0; // Set that will contains unsorted // elements HashSet< int > s = new HashSet< int >(); // Iterating through the elements for ( int i = 0; i < n; i++) { // Inserting the required elements // in the set if (i != A[i]) { count++; s.Add(i); } } // When the given array is // already sorted if (count == 0) { Console.WriteLine( "0" ); } else { // Vector that will contain // the answer List<List< int >> ans = new List<List< int >>(); // Temporary vector to store // the indices List< int > vv = new List< int >(); int x, y, z; count = 0; // Loop that will execute till the // set becomes empty while (s.Count > 0) { var it = s.GetEnumerator(); it.MoveNext(); // Check for the condition int i = it.Current; if (i == A[A[i]]) { s.Remove(i); s.Remove(A[i]); continue ; } // Case when the minimum two else { x = A[i]; y = A[A[i]]; z = A[A[A[i]]]; vv.Add(x); vv.Add(y); vv.Add(z); // Changing the order of elements cngorder(A, x, y, z); // Pushing the indices to the // answer vector ans.Add( new List< int >(vv)); // If the third element also // gets sorted if (vv[0] == A[vv[0]]) { s.Remove(vv[0]); } // Erasing the two sorted elements // from the set s.Remove(vv[1]); s.Remove(vv[2]); vv.Clear(); } } count = 0; // The count of the remaining // unsorted elements for ( int i = 0; i < n; i++) { if (i != A[i]) { count++; } } // If the count of the left // unsorted elements is not // a multiple of 4, then // sorting is not possible if (count % 4 != 0) { flag = true ; } // Only the elements such that // i = A[A[i]] are left // for sorting else { // Indices of any one element // from the two pairs that // will be sorted in 2 steps int i1 = -1, i2 = -1; for ( int i = 0; i < n; i++) { // Index of any element of // the pair if (A[i] != i && i1 == -1) { i1 = i; } // When we find the second // pair and the index of // any one element is stored else if (A[i] != i && i1 != -1 && i2 == -1) { if (i1 == A[i]) continue ; else i2 = i; } if (i1 != -1 && i2 != -1) { // Remaining two indices // of the elements int i3 = A[i1], i4 = A[i2]; // The first order of indices vv.Add(i1); vv.Add(i2); vv.Add(A[i1]); // Pushing the indices to the // answer vector ans.Add( new List< int >(vv)); vv.Clear(); // The second order of indices vv.Add(i2); vv.Add(A[i1]); vv.Add(A[i2]); // Pushing the indices to the // answer vector ans.Add( new List< int >(vv)); vv.Clear(); // Changing the order of the // first combination of // the indices cngorder(A, i1, i2, i3); // Changing the order of the // second combination of // the indices after which all // the 4 elements will be sorted cngorder(A, i2, i3, i4); i1 = -1; i2 = -1; } } } // If the flag value is 1 // the sorting is not possible if (flag) { Console.WriteLine( "-1" ); } else { // Printing the required number // of steps Console.WriteLine(ans.Count); // Printing the indices involved // in the shifting for ( int i = 0; i < ans.Count; i++) { Console.WriteLine(ans[i][0] + " " + ans[i][1] + " " + ans[i][2]); } } } } // Driver code static void Main( string [] args) { List< int > A = new List< int > { 0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11 }; int n = A.Count; sortbyorder3(A, n); } } //This code is contributed by Shivhack999 |
Javascript
// Function to change the order of // the elements having a temporary // array and the required indices function cngorder(v, i, j, k) { let temp = v[k]; v[k] = v[j]; v[j] = v[i]; v[i] = temp; } // Function to sort the elements having // the given array and its size. function sortbyorder3(A, n) { // Flag to check whether the sorting // is possible or not let flag = 0; let count = 0; // Set that will contain unsorted // elements let s = new Set(); // Iterating through the elements for (let i = 0; i < n; i++) { // Inserting the required elements // in the set if (i !== A[i]) count++, s.add(i); } // When the given array is // already sorted if (count === 0) console.log( "0" ); else { // Array that will contain // the answer let ans = []; // Temporary array to store // the indices let vv = []; let x, y, z; count = 0; // Loop that will execute till the // set becomes empty while (s.size !== 0) { let it = s.values().next().value; let i = it; // Check for the condition if (i === A[A[i]]) { s. delete (i); s. delete (A[i]); continue ; } // Case when the minimum two // elements will get sorted else { x = A[i], y = A[A[i]], z = A[A[A[i]]]; vv.push(x), vv.push(y), vv.push(z); // Changing the order of elements cngorder(A, x, y, z); // Pushing the indices to the // answer array ans.push([...vv]); // If the third element also // gets sorted if (vv[0] === A[vv[0]]) s. delete (vv[0]); // Erasing the two sorted elements // from the set s. delete (vv[1]); s. delete (vv[2]); vv = []; } } count = 0; // The count of the remaining // unsorted elements for (let i = 0; i < n; i++) { if (i !== A[i]) count++; } // If the count of the left // unsorted elements is not // a multiple of 4, then // sorting is not possible if (count % 4 !== 0) flag = 1; // Only the elements such that // i = A[A[i]] are left // for sorting else { // Indices of any one element // from the two pairs that // will be sorted in 2 steps let i1 = -1, i2 = -1; for (let i = 0; i < n; i++) { // Index of any element of // the pair if (A[i] !== i && i1 === -1) { i1 = i; } // When we find the second // pair and the index of // any one element is stored else if (A[i] !== i && i1 !== -1 && i2 === -1) { if (i1 === A[i]) continue ; else i2 = i; } // When we got both the pair // of elements if (i1 !== -1 && i2 !== -1) { // Remaining two indices // of the elements let i3 = A[i1], i4 = A[i2]; // The first order of indices vv.push(i1), vv.push(i2), vv.push(i3); // Pushing the indices to the // answer array ans.push([...vv]); vv = []; // The second order of indices vv.push(i2), vv.push(i3), vv.push(i4); // Pushing the indices to the // answer array ans.push([...vv]); vv = []; // Changing the order of the // first combination of // the indices cngorder(A, i1, i2, i3); // Changing the order of the // second combination of // the indices after which all // the 4 elements will be sorted cngorder(A, i2, i3, i4); i1 = -1, i2 = -1; } } } // If the flag value is 1 // the sorting is not possible if (flag === 1) console.log( "-1" ); else { // Printing the required number // of steps console.log(ans.length); // Printing the indices involved // in the shifting for (let i = 0; i < ans.length; i++) { console.log(ans[i][0], ans[i][1], ans[i][2]); } } } } // Driver code function main() { let n; let A = [0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11]; n = A.length; // Calling the sorting function sortbyorder3(A, n); } // Invoke the main function main(); |
6 11 5 7 11 4 1 11 8 3 11 10 6 2 11 9 11 9 12
Time Complexity: O(N), where N is the size of the array.
Auxiliary space: O(N)
Contact Us