Блог

Задан целочисленный круговой массив v с n> 0 числами, и только один возможный ход «m» — поменять один элемент на один после 2 впереди.
Я должен напечатать последовательность ходов, которые сортируют v или говорят, что это невозможно (на языке c)

Пример:
начальный: v = [8, 0, 5, 9, -1, 5]
после применения m к v[4]: v = [-1, 0, 5, 9, 8, 5]
после применения m к v[3]: v = [-1, 0, 5, 5, 8, 9]
, который теперь сортируется с позиции 0. Результат будет «4 3»

Что я знаю до этого момента:
— Если есть нечетное количество элементов, вы можете переместить любой элемент в любую позицию. (Но достаточно ли этого, чтобы гарантировать, что он может быть отсортирован?)
— Для четного числа элементов не всегда возможно отсортировать его, поскольку вы не можете перемещать элементы между четными и нечетными позициями (например: v = [-1, -2, 1, 7], невозможно, потому что -2 дюйма — нечетная позиция, но должно быть в четной позиции).

Я думал об этом:
— Используйте вспомогательный массив «aux», чтобы поместить числа с их реальными соседями, например:
v = [8, 0, 5, 9, -1, 5, 6] -> вспомогательный = [8, 5, -1, 6, 0, 9,5]
Теперь в aux я могу выполнять простые замены с номерами смежных элементов.
— Окончательная конфигурация с точки зрения их позиции «i» в aux:
v = [8, 0, 5, 9, -1, 5, 6] -> вспомогательный = [8, 5, -1, 6, 0, 9, 5] -> i = [0, 2, 4, 6, 1, 3, 5]
— Если n четное, то будет 2 дополнительных, потому что для сортировки v вы не можете перемещать числа между четными и нечетными позициями, поэтому возникает 2 дополнительные проблемы. Пример:
v = [8, 0, 5, 9, -1, 5]
aux-четный = [8, 5, -1] -> i-четный = [0, 2, 4]
aux-нечетный = [0, 9, 5] -> i-четный = [1, 3, 5] (мышление в терминах v)

Я не уверен, куда идти отсюда или если это даже хороший путь для запуска.

Любые идеи или помощь приветствуются.

Редактировать

Я пытаюсь смоделировать алгоритм, предложенный AlexD для нечетного случая:
v = [8, 0, 5, 9, -1, 5, 6]
v-сортированный = [-1, 0, 5, 5, 6, 8, 9]

Назначение им ключей (-1, 1), (0, 5), (5, 2), (5, 6), (6, 3), (8, 7), (9, 4).

Возврат к исходному порядку:
(8, 7) (0, 5) (5, 2) (9, 4) (-1, 1) (5, 6) (6, 3)

Использование пузырьковой сортировки для ключей с 1 между ними.
(8, 7) (0, 5) (5, 2) (9, 4) (-1, 1) (5, 6) (6, 3)
(5, 2) (0, 5) (8, 7) (9, 4) (-1, 1)(5, 6) (6, 3)
(5, 2) (0, 5) (-1, 1) (9, 4) (8, 7) (5, 6) (6, 3)
(5, 2) (0, 5) (-1, 1)(9, 4) (6, 3) (5, 6) (8, 7)
(-1, 1) (0, 5) (5, 2) (9, 4) (6, 3) (5, 6) (8, 7)
(-1, 1)(9, 4) (5, 2) (0, 5) (6, 3) (5, 6) (8, 7)
(-1, 1) (9, 4) (5, 2) (0, 5) (6, 3) (5, 6)(8, 7)
Но числа не сортируются. Чего мне не хватает?

Для краткости позвольте мне проиллюстрировать идею конкретными примерами, которые легко обобщить.

Четный случай

Допустим, у нас есть 8 элементов. Затем мы сортируем два подмассива (с четными и нечетными индексами) отдельно, используя пузырьковую сортировку на шаге 2, и имеем

 a1    a2    a3    a4
   b1    b2    b3    b4
 

Если результирующий массив a1 b1 a2 b2 a3 b3 a4 b4 был отсортирован, мы закончили. В противном случае решения нет.

Нечетный случай

Допустим, у вас есть 7 элементов. Сортируйте их своим любимым методом. Допустим, после сортировки они

 a5 a4 a1 a7 a3 a2 a6
 

Назначьте ключ каждому элементу следующим образом:

 a5 a4 a1 a7 a3 a2 a6
 1  5  2  6  3  7  4
 

Затем вернитесь к исходному порядку:

 a1 a2 a3 a4 a5 a6 a7
 2  7  3  5  1  4  6
 

Затем отсортируйте пары по новым ключам ( 1 — 7 ), используя пузырьковую сортировку и каждый раз перепрыгивая через один элемент. Как только вы отсортируете ключи, ваши a1 … a7 значения займут свои позиции назначения.

Давайте проиллюстрируем это с помощью массива

 5 1 5 9 0
 

Отсортированный массив и соответствующие ключи будут

 0 1 5 5 9
1 4 2 5 3
 

Теперь давайте отсортируем пары по ключу (пары, ключи которых мы сравниваем по одному на каждом шаге <> )

 <5 2> (1 4) <5 5> (9 3) (0 1) // starting the first loop
(5 2) (1 4) <5 5> (9 3) <0 1>
(5 2) <1 4> (0 1) (9 3) <5 5>
(5 2) <5 5> (0 1) <9 3> (1 4)
<5 2> (9 3) <0 1> (5 5) (1 4) // (5 5) is in its final position, starting the second loop
(0 1) (9 3) <5 2> (5 5) <1 4>
(0 1) <9 3> (5 2) (5 5) <1 4>
<0 1> (1 4) <5 2> (5 5) (9 3) // (1 4) in its final position, starting the third loop
(0 1) (1 4) <5 2> (5 5) <9 3>
<0 1> (1 4) <5 2> (5 5) (9 3) // (9 3) in the final position
(0 1) (1 4) (5 2) (5 5) (9 3) // (0 1) and (5 2) are in final positions