Programa C++ para verificar si es posible ordenar la array después de rotarla

Dada una array de tamaño N, la tarea es determinar si es posible ordenar la array o no con solo una mezcla. En una mezcla, podemos mover algunos elementos contiguos desde el final de la array y colocarlos al frente de la array.
Por ejemplo: 
 

1. A = {2, 3, 1, 2}, podemos desplazar {1, 2} desde el final del arreglo al frente del arreglo para ordenarlo.
2. A = {1, 2, 3, 2} ya que no podemos ordenarlo de una sola vez, por lo tanto, no es posible ordenar la array.

Ejemplos: 
 

Input: arr[] = {1, 2, 3, 4} 
Output: Possible 
Since this array is already sorted hence no need for shuffle.

Input: arr[] = {6, 8, 1, 2, 5}
Output: Possible
Place last three elements at the front 
in the same order i.e. {1, 2, 5, 6, 8}

Acercarse: 
 

1. Compruebe si la array ya está ordenada o no. Si es así, devuelve verdadero.
2. De lo contrario, comience a recorrer los elementos de la array hasta que el elemento actual sea más pequeño que el siguiente. Almacene ese índice donde arr[i] > arr[i+1].
3. Recorra desde ese punto y verifique si los elementos de ese índice están en orden creciente o no.
4. Si se cumplen las dos condiciones anteriores, compruebe si el último elemento es menor o igual que el primer elemento de la array dada.
5. Escriba «Posible» si se cumplen las tres condiciones anteriores; de lo contrario, escriba «No es posible» si falla alguna de las 3 condiciones anteriores.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
bool isPossible(int a[], int n)
{
    // step 1
    if (is_sorted(a, a + n)) {
        cout << "Possible" << endl;
    }
 
    else {
 
        // break where a[i] > a[i+1]
        bool flag = true;
        int i;
        for (i = 0; i < n - 1; i++) {
            if (a[i] > a[i + 1]) {
                break;
            }
        }
        // break point + 1
        i++;
 
        // check whether the sequence is
        // further increasing or not
        for (int k = i; k < n - 1; k++) {
            if (a[k] > a[k + 1]) {
                flag = false;
                break;
            }
        }
 
        // If not increasing after break point
        if (!flag)
            return false;
 
        else {
 
            // last element <= First element
            if (a[n - 1] <= a[0])
                return true;
 
            else
                return false;
        }
    }
}
 
// Driver code
int main()
{
 
    int arr[] = { 3, 1, 2, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    if (isPossible(arr, n))
        cout << "Possible";
 
    else
        cout << "Not Possible";
 
    return 0;
}

Possible

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)

Consulte el artículo completo sobre Comprobar si es posible ordenar la array después de rotarla para obtener más detalles.