整数の円形配列を1つの要素に入れ替えて並べ替え

Question

n> 0の整数の循環配列vを指定すると、1つの要素を2つ先の要素と入れ替えることができます。
IソートV移動のシーケンスを印刷したり、それは（C言語では）不可能だと言う

例なければならない：
初期V = [8,0、5、9、-1、5]
Vに対するMを適用した後、[4]：V = -1、0、5、9、、5]
VにMを適用した後、[3]：V = [-1、0、5、 ,8,
これは現在0の位置からソートされています。
- 奇数の要素がある場合、任意の要素を任意の位置に移動できます。
- 奇数の要素がある場合は、任意の要素を任意の位置に移動できます。
- 偶数の要素の場合、要素を奇数と偶数の位置間で移動することはできないため、常にソートすることはできません（例：v = [ - 1、-2、1、7]であり、-2 inが奇数位置であるが偶数位置にある必要があるため不可能である）。

私はこのことについて考えてきた：
- "AUX" のように、彼らの真の隣人と数字を入れてAUXILIAR配列を使用します。[
V = 8、0、5、9、-1、5 、6] - > aux = [8,5、-1、6、0、9、5]
これでAUXで簡単に隣接番号を入れ替えられます。
- auxの位置 "i"に関する最終的な設定は、
v = [8、0、5、9、-1、5,6] - > aux = [8,5、-1、 0、9、5] - > i = [0,2,4,6,1,3,5]
- nが偶数の場合、vをソートするために2つのauxが存在します。奇数と偶数の間の数字を移動するので、2つの問題があります。例：
v = [8,0,5,9、-1,5]
aux-even = [8,5、-1] - i-even = [0,2,4]
aux -odd = [0,9,5] - > i-even = [1,3,5]（vの点で考えると）

ここからどこへ行くのか、それとも良い道であればわからない走る。

アイデアや助けを歓迎します。

EDIT

Iが奇数の場合のAlexDによって提案されたアルゴリズムをシミュレートしようとしている[8、0、5、9、-1、5、6]
Vソート
V =を= [-1、0、5、5、6、8、9]

それらにキー（-1、）、（0、）、（5、）を割り当て、（ 5,）、（6,）、（8,）、（9,）。元の順序に

：
（8,7）（0,5）（5,2）（9,4）（ - 1,1）（5,6）（6,3）

キーの間に1を使用するバブルソートを使用します。 （0、5）（5、2）（9,4）（-1,1）（5,6）（6,3）
,（0,0）（-1,）（1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,26） （5,4）（8,）（5,6）（6,3）
（0,5）（-1,1）（9,4）（6,）（5、6）（8、）
（-1、）（0,5）（5、2,1,230,588,5）（0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28） （5,6）（5,6）（5,6）（5,6）（8,7）
（-1、 7）
しかし、番号はソートされません。私は何が欠けていますか？

Answer 1

簡潔にするために、一般化が容易な具体的なケースでアイデアを説明しましょう。

場合でも

は、我々は8つの要素を持っているとしましょう。その後、我々ソートサブアレイ（奇数および偶数インデックスを有する）を別々に2つのステップ2でバブルソートを使用して、そして

a1 a2 a3 a4 
    b1 b2 b3 b4 

を有する得られた配列a1 b1 a2 b2 a3 b3 a4 b4をソートするが起こった場合、我々が行われています。それ以外の場合、解決策はありません。

奇数の場合

は、あなたが、7つの要素を持っているとしましょう。お気に入りの方法で並べ替えます。次に、新しいことでペアを並べ替える

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

：次に

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

元の順序に戻ってくる：者は、ソートした後、彼らはこのようなすべての要素に

a5 a4 a1 a7 a3 a2 a6 

Assignキーあるとしましょうキー（1 - 7）を使用して、バブルソートを使用し、毎回1つの要素にジャンプします。キーがソートされるとすぐに、a1 ... a7の値が目的地になります。

ソートされた配列とそれに対応するキーが

0 1 5 5 9 
1 4 2 5 3 

が今度は（そのキー我々は1ステップごとの比較ペアが<>である）キーでペアをソートしてみましょうだろうのは、配列

5 1 5 9 0 

で説明してみましょう

<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