algorithm
奇数偶数ソート

奇数 - 偶数基本情報のソート

奇数 - 偶数ソートまたはレンガソートは、ローカル相互接続を持つ並列プロセッサで使用するために開発された単純なソートアルゴリズムです。これは、リスト内の隣接する要素のすべての奇数/偶数のインデックス付きペアを比較することによって機能し、ペアが間違った順序にある​​場合、要素が切り替わります。次のステップでは、偶数/奇数のインデックス付きペアに対してこれを繰り返します。次に、リストがソートされるまで、奇数/偶数ステップと奇数/奇数ステップの間で交互に切り替わります。

奇数 - 偶数ソートの疑似コード：

if n>2 then
    1. apply odd-even merge(n/2) recursively to the even subsequence a0, a2, ..., an-2 and to the odd subsequence a1, a3, , ..., an-1
    2. comparison [i : i+1] for all i element {1, 3, 5, 7, ..., n-3}
else
    comparison [0 : 1]

ウィキペディアには、奇数 - 偶数の並べ替えのベストイラストがあります：

奇数偶数ソートの例：

実装：

奇数 - 偶数ソートアルゴリズムを実装するためにC＃言語を使用しました。

public class OddEvenSort
{
    private static void SortOddEven(int[] input, int n)
    {
        var sort = false;

        while (!sort)
        {
            sort = true;
            for (var i = 1; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
            for (var i = 0; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortOddEven(input, input.Length);
        return input;
    }
}

補助空間： O(n)
時間の複雑さ： O(n)