Программа Php для проверки возможности сортировки массива после его поворота

Учитывая массив размера N, задача состоит в том, чтобы определить, можно ли отсортировать массив всего за одну перетасовку. За один раз мы можем сдвинуть несколько смежных элементов с конца массива и поместить их в начало массива.
Например:

1. A = {2, 3, 1, 2}, we can shift {1, 2} from the end of the array to the front of the array to sort it.
2. A = {1, 2, 3, 2} since we cannot sort it in one shuffle hence it’s not possible to sort the array.

Примеры:

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}

Подход:

1. Проверьте, отсортирован ли массив уже или нет. Если да, верните true.
2. В противном случае начните обход элементов массива, пока текущий элемент не станет меньше следующего элемента. Сохраните этот индекс, где arr[i] > arr[i+1].
3. Пройдите от этой точки и проверьте, находятся ли элементы этого индекса в порядке возрастания или нет.
4. Если выше оба условия выполнены, проверьте, меньше ли последний элемент первого элемента данного массива или равен ему.
5. Выведите «Возможно», если выполняются три вышеуказанных условия, иначе выведите «Невозможно», если любое из трех вышеуказанных условий не выполнено.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(n)
Вспомогательное пространство: O(1)

Пожалуйста, обратитесь к полной статье о проверке возможности сортировки массива после его вращения для получения более подробной информации!