Ordenar la permutación decreciente de N usando intercambios triples

Dada una array A[] que consiste en una permutación decreciente de N números, la tarea es ordenar la array utilizando intercambios triples. Si no es posible ordenar la array, imprima -1.  

Los swaps triples se refieren al desplazamiento cíclico a la derecha en los índices elegidos. Desplazamiento cíclico a la derecha: x –> y –> z –> x. 

Ejemplos:  

Entrada: A[] = {4, 3, 2, 1} 
Salida: 1 2 3 4 
Explicación: 
Para la array dada, el primer paso es elegir índices: x = 0, y = 2, z = 3 
Por lo tanto, A[3 ] = A[2]; A[2] = A[0]; A[0] = A[3]. 
Antes de intercambiar: 4 3 2 1 y después de intercambiar: 1 3 4 2.
Para la array dada, el segundo paso es elegir índices: x = 1, y = 2, z = 3 Por lo tanto, A[3] = A[2]; A[2] = A[1]; A[1] = A[3]. 
Antes de intercambiar: 1 3 4 2 y después de intercambiar: 1 2 3 4.
Entrada: A[] = {5, 4, 3, 2, 1} 
Salida: 1 2 3 4 5 
Explicación: 
Para la array dada, el primer paso es eligiendo índices: x = 0, y = 3, z = 4 por lo tanto, 
A[4] = A[3]; A[3] = A[0]; A[0] = A[4], antes de intercambiar: 5 4 3 2 1 y después de intercambiar: 1 4 3 5 2 
Para la array dada, el segundo paso es elegir índices: x = 1, y = 3, z = 4, por lo tanto , 
A[4] = A[3]; A[3] = A[1]; A[1] = A[4], antes del intercambio: 1 4 3 5 2 y después del intercambio: 1 2 3 4 5  

Enfoque: 
Para resolver el problema mencionado anteriormente, debemos elegir tres índices de tal manera que podamos llevar al menos un elemento a la posición correcta . Con eso queremos decir que tenemos que llevar 1 al índice 0, 2 al índice 1, y así sucesivamente.  

1. x se elige como el número de índice actual i,
2. z se elige como el índice de x + 1 que siempre es N – i – 1 y
3. y se elige en consecuencia.

Luego tenemos que realizar el intercambio de elementos mediante el desplazamiento cíclico a la derecha de elementos usando estos índices.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation to sort
// decreasing permutation of N
// using triple swaps
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort Array
void 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 code
int main()
{
 
    int A[] = { 5, 4, 3, 2, 1 };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    sortArray(A, N);
 
    return 0;
}

// Java implementation to sort
// decreasing permutation of N
// using triple swaps
 
class GFG{
 
// Function to sort array
static 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 code
public 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 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# implementation to sort
// decreasing permutation of N
// using triple swaps
using System;
class GFG{
 
// Function to sort array
static 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 code
public 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

<script>
 
// Javascript implementation to sort
// decreasing permutation of N
// using triple swaps
 
// Function to sort array
function 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

Complejidad temporal: O(n)
Espacio auxiliar: O(1)