Сортировка массива путем сдвига вправо любых трех элементов массива

Question

У меня есть массив из N целых чисел, таких что 1 ≤ a [i] ≤ N. (перестановка N целых чисел).

ie для элементов массива может быть 5,1,2,3,4.

Мне нужно отсортировать массив, выбрав любые три индекса a [p], a [q], a [r] и выполнить операцию сдвига вправо ...

Что будет быть минимальным числом операций для сортировки массива?

Для этого массива 5, 8, 6, 3, 7, 9, 2, 1, 10, 4 ответ 5, а индексы для смещения:

1 5 7;
1 2 8;
3 6 9;
3 4 10;
3 4 10;

Answer 1

Интересная задача.

Посмотрим - мы начинаем с

 5 8 6 3 7 9 2 1 10 4

Вращение вправо на одну позицию, хотя смещения 1, 2, 8 (на основе 1) дает

 1 5 6 3 7 9 2 8 10 4

Итак, теперь 1 и 8 находятся в своих конечных положениях

Затем, вращение через 4, 9, 10 дает

 1 5 6 4 7 9 2 8 3 10

Теперь 1, 4, 8 и 10 находятся в их окончательном положении

Затем, вращение через 3, 6, 9 дает

 1 5 3 4 7 6 2 8 9 10

Теперь 1, 3, 4, 6, 8, 9 и 10 находятся в их окончательном положении

Наконец, вращение на 2, 5, 7 дает

 1 2 3 4 5 6 7 8 9 10

Итак, 4 вращения.

Теперь я сделал это вручную. Разработка алгоритма для поиска подобных решений оставлена ​​читателю в качестве упражнения;)