Сортировать заданный массив, используя не более N циклических сдвигов в любом подмассиве

Дан массив arr[] , содержащий N целых чисел, с дубликатами. Задача состоит в том, чтобы отсортировать массив в порядке возрастания, используя не более N циклических сдвигов на любом подмассиве.

Cyclic shift on any sub-array means cut out any subarray from the given array, use cyclic shift (rotate) in it by any offset, and put it back into the same place of the array. 

Выведите количество таких сдвигов, необходимых для сортировки массива. Возможностей может быть несколько.

Примеры:

Input: arr[] = [1, 3, 2, 8, 5]
Output: 2
Explanation: Consider segment from index = 1 to index = 2. [1, 3, 2, 8, 5]. Now rotate this segment by 1 offset. The new array becomes, [1, 2, 3, 8, 5]. 
Then consider segment from index = 3 to index = 4, [1, 2, 3, 8, 5]. Rotate it by 1 offset, the new array becomes, [1, 2, 3, 5, 8].

Input: arr[] = [2, 4, 1, 3]
Output: 2
Explanation: From index = 0 to index = 2, [2, 4, 1, 3]. Rotate this segment by 2 offset on left, the new array becomes, [1, 2, 4, 3]. 
Taking second segment from index = 2 to index = 3 of offset 1, rotate it the new array becomes, [1, 2, 4, 3].

Подход: может быть два случая:

1. Случай, когда массив уже отсортирован: Тогда нам не нужно выполнять никаких операций сдвига
2. Случай, когда массив не отсортирован: Для этого выполните шаги, указанные ниже:
   • Создайте переменную count = 0 для хранения общего количества подсчетов.
   • Итерация от i = 0 до i = N-2 . И для каждой итерации выполните следующие операции:
     • Создайте переменную minVal для хранения минимального значения, найденного в этой итерации, и инициируйте ее со значением arr[i] .
     • Начните итерацию от i+1 до N-1 . Если текущее значение меньше minVal, обновите minVal .
     • Отметьте эту позицию справа , чтобы выполнить циклический сдвиг от i вправо на смещение 1.
   • Если такого правильного значения не существует, просто перейдите к следующей итерации .
   • В противном случае поверните массив от i вправо на 1 позицию и увеличьте счетчик на 1.
   • Верните значение count в качестве ответа.

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

Временная сложность: O(N ² )
Космическая сложность: O(1)