Given an array A[] consisting of decreasing permutation of N numbers, the task is to sort the array using triple swaps. If it is not possible to sort the array then print -1.
Triple swaps refer to cyclic right shift on chosen indices. Cyclic Right Shift: x –> y –> z –> x.
Examples:
Input: A[] = {4, 3, 2, 1}
Output: 1 2 3 4
Explanation:
For the given array the first step is choosing indexes: x = 0, y = 2, z = 3
Therefore, A[3] = A[2]; A[2] = A[0]; A[0] = A[3].
Before Swapping: 4 3 2 1 and After Swapping: 1 3 4 2.
For the given array the second step is choosing indexes: x = 1, y = 2, z = 3 Therefore, A[3] = A[2]; A[2] = A[1]; A[1] = A[3].
Before Swapping: 1 3 4 2 and After Swapping: 1 2 3 4.
Input: A[] = {5, 4, 3, 2, 1}
Output: 1 2 3 4 5
Explanation:
For the given array the first step is choosing indexes: x = 0, y = 3, z = 4 therefore,
A[4] = A[3]; A[3] = A[0]; A[0] = A[4], Before Swapping: 5 4 3 2 1 and After Swapping: 1 4 3 5 2
For the given array the second step is choosing indexes: x = 1, y = 3, z = 4 therefore,
A[4] = A[3]; A[3] = A[1]; A[1] = A[4], Before Swapping: 1 4 3 5 2 and After Swapping: 1 2 3 4 5
Approach:
To solve the problem mentioned above we have to choose three indexes in such a way so that we can bring at least one element at the correct position. By that, we mean that we have to bring 1 at index 0, 2 at index 1, and so on.
- x is chosen as the current index number i,
- z is chosen as the index of x + 1 which is always N – i – 1 and
- y is chosen accordingly.
Then we have to perform the swapping of elements by the cyclic right shift of elements using these indices.
Below is the implementation of the above approach:
C++
// C++ implementation to sort// decreasing permutation of N// using triple swaps#include <bits/stdc++.h>using namespace std;// Function to sort Arrayvoid sortArray(int A[], int N){ // The three indices that // has to be chosen int x, y, z; // Check if possible to sort array if (N % 4 == 0 || N % 4 == 1) { // Swapping to bring element // at required position // Bringing at least one // element at correct position for (int i = 0; i < N / 2; i++) { x = i; if (i % 2 == 0) { y = N - i - 2; z = N - i - 1; } // Tracing changes in Array A[z] = A[y]; A[y] = A[x]; A[x] = x + 1; } // Print the sorted array cout << "Sorted Array: "; for (int i = 0; i < N; i++) cout << A[i] << " "; } // If not possible to sort else cout << "-1";}// Driver codeint main(){ int A[] = { 5, 4, 3, 2, 1 }; int N = sizeof(A) / sizeof(A[0]); sortArray(A, N); return 0;} |
Java
// Java implementation to sort// decreasing permutation of N// using triple swapsclass GFG{// Function to sort arraystatic void sortArray(int A[], int N){ // The three indices that // has to be chosen int x = 0, y = 0, z = 0; // Check if possible to sort array if (N % 4 == 0 || N % 4 == 1) { // Swapping to bring element // at required position // Bringing at least one // element at correct position for(int i = 0; i < N / 2; i++) { x = i; if (i % 2 == 0) { y = N - i - 2; z = N - i - 1; } // Tracing changes in array A[z] = A[y]; A[y] = A[x]; A[x] = x + 1; } // Print the sorted array System.out.print("Sorted Array: "); for(int i = 0; i < N; i++) System.out.print(A[i] + " "); } // If not possible to sort else { System.out.print("-1"); }}// Driver codepublic static void main(String[] args){ int A[] = { 5, 4, 3, 2, 1 }; int N = A.length; sortArray(A, N);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to sort # decreasing permutation of N # using triple swaps # Function to sort array def sortArray(A, N): # Check if possible to sort array if (N % 4 == 0 or N % 4 == 1): # Swapping to bring element # at required position # Bringing at least one # element at correct position for i in range(N // 2): x = i if (i % 2 == 0): y = N - i - 2 z = N - i - 1 # Tracing changes in Array A[z] = A[y] A[y] = A[x] A[x] = x + 1 # Print the sorted array print("Sorted Array: ", end = "") for i in range(N): print(A[i], end = " ") # If not possible to sort else: print("-1") # Driver code A = [ 5, 4, 3, 2, 1 ] N = len(A) sortArray(A, N)# This code is contributed by yatinagg |
C#
// C# implementation to sort// decreasing permutation of N// using triple swapsusing System;class GFG{// Function to sort arraystatic void sortArray(int []A, int N){ // The three indices that // has to be chosen int x = 0, y = 0, z = 0; // Check if possible to sort array if (N % 4 == 0 || N % 4 == 1) { // Swapping to bring element // at required position // Bringing at least one // element at correct position for(int i = 0; i < N / 2; i++) { x = i; if (i % 2 == 0) { y = N - i - 2; z = N - i - 1; } // Tracing changes in array A[z] = A[y]; A[y] = A[x]; A[x] = x + 1; } // Print the sorted array Console.Write("Sorted Array: "); for(int i = 0; i < N; i++) Console.Write(A[i] + " "); } // If not possible to sort else { Console.Write("-1"); }}// Driver codepublic static void Main(String[] args){ int []A = { 5, 4, 3, 2, 1 }; int N = A.Length; sortArray(A, N);}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript implementation to sort// decreasing permutation of N// using triple swaps// Function to sort arrayfunction sortArray(A, N){ // The three indices that // has to be chosen let x = 0, y = 0, z = 0; // Check if possible to sort array if (N % 4 == 0 || N % 4 == 1) { // Swapping to bring element // at required position // Bringing at least one // element at correct position for(let i = 0; i < N / 2; i++) { x = i; if (i % 2 == 0) { y = N - i - 2; z = N - i - 1; } // Tracing changes in array A[z] = A[y]; A[y] = A[x]; A[x] = x + 1; } // Print the sorted array document.write("Sorted Array: "); for(let i = 0; i < N; i++) document.write(A[i] + " "); } // If not possible to sort else { document.write("-1"); }}// Driver Code let A = [ 5, 4, 3, 2, 1 ]; let N = A.length; sortArray(A, N); </script> |
Sorted Array: 1 2 3 4 5
Time Complexity: O(n)
Auxiliary Space: O(1)
