Programa C++ para verificar si una array está ordenada y rotada

Dada una array de N enteros distintos. La tarea es escribir un programa para verificar si esta array está ordenada y girada en sentido contrario a las agujas del reloj. Una array ordenada no se considera ordenada y rotada, es decir, debe haber al menos una rotación.
Ejemplos : 
 

Input : arr[] = { 3, 4, 5, 1, 2 }
Output : YES
The above array is sorted and rotated.
Sorted array: {1, 2, 3, 4, 5}. 
Rotating this sorted array clockwise 
by 3 positions, we get: { 3, 4, 5, 1, 2}

Input: arr[] = {7, 9, 11, 12, 5}
Output: YES

Input: arr[] = {1, 2, 3}
Output: NO

Input: arr[] = {3, 4, 6, 1, 2, 5}
Output: NO

Enfoque : 
 

• Encuentre el elemento mínimo en la array.
• Ahora, si se ordena la array y luego se giran todos los elementos antes del elemento mínimo estarán en orden creciente y todos los elementos después del elemento mínimo también estarán en orden creciente.
• Compruebe si todos los elementos antes del elemento mínimo están en orden creciente.
• Compruebe si todos los elementos después del elemento mínimo están en orden creciente.
• Compruebe si el último elemento de la array es más pequeño que el elemento inicial.
• Si se cumplen las tres condiciones anteriores, imprima SÍ ; de lo contrario, imprima NO .

A continuación se muestra la implementación de la idea anterior: 
 

// CPP program to check if an array is
// sorted and rotated clockwise
#include <climits>
#include <iostream>
 
using namespace std;
 
// Function to check if an array is
// sorted and rotated clockwise
void checkIfSortRotated(int arr[], int n)
{
    int minEle = INT_MAX;
    int maxEle = INT_MIN;
 
    int minIndex = -1;
 
    // Find the minimum element
    // and it's index
    for (int i = 0; i < n; i++) {
        if (arr[i] < minEle) {
            minEle = arr[i];
            minIndex = i;
        }
    }
 
    int flag1 = 1;
 
    // Check if all elements before minIndex
    // are in increasing order
    for (int i = 1; i < minIndex; i++) {
        if (arr[i] < arr[i - 1]) {
            flag1 = 0;
            break;
        }
    }
 
    int flag2 = 1;
 
    // Check if all elements after minIndex
    // are in increasing order
    for (int i = minIndex + 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            flag2 = 0;
            break;
        }
    }
 
    // Check if last element of the array
    // is smaller than the element just
    // starting element of the array
    // for arrays like [3,4,6,1,2,5] - not circular array
    if (flag1 && flag2 && (arr[n - 1] < arr[0]))
        cout << "YES";
    else
        cout << "NO";
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 5, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    checkIfSortRotated(arr, n);
    return 0;
}

YES

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Consulte el artículo completo sobre Comprobar si una array está ordenada y rotada para obtener más detalles.