奇遇転置ソートとは

奇遇転置ソートとは、交換ソートの一種であり、バブルソートの改良版ソートアルゴリズムです。隣り合った要素同士を順次交換するバブルソートと異なり、要素番号が奇数偶数のペア同士で交換を行います。

ソートの特性としてはバブルソートと同じく、安定 な 内部 ソートです。計算量も O(n2) と低速ですが、このソートアルゴリズムの特徴は、ペア同士の比較交換処理が互いに独立しているため、並列処理を行える点にあります。

奇遇転置ソートのシミュレーション

(偶数, 奇数) ペア と (奇数, 偶数) ペア それぞれの組み合わせで交換が行われることがわかります。

アルゴリズムの解説

ソート対象のデータの先頭から、要素番号が (偶数, 奇数) となるペアで比較交換を行います。続けて要素番号が (奇数, 偶数) となるペアで比較交換を行います。後は上記の処理を交換ができない状態になるまで続けます。交換できなくなればソート完了です。

(偶数, 奇数)ペア => (0, 1), (2, 3), (4, 5) ...

(奇数, 偶数)ペア => (1, 2), (3, 4), (5, 6) ...

並列処理

ペア内の組み合わせはそれぞれ独立しているので、この部分を並列化することができます。

サンプルコード

C#

public static void OddEvenSort<T>(T[] arr) where T : IComparable<T>
{
    int n = arr.Length;
    bool isSwaped = false;

    do
    {
        isSwaped = false;

        // (偶数, 奇数)ペアの比較交換
        for (int i = 0; i < n - 1; i += 2)
        {
            if (arr[i + 1].CompareTo(arr[i]) < 0)
            {
                Swap(ref arr[i + 1], ref arr[i]);
                isSwaped = true;
            }
        }

        // (奇数, 偶数)ペアの比較交換
        for (int i = 1; i < n - 1; i += 2)
        {
            if (arr[i + 1].CompareTo(arr[i]) < 0)
            {
                Swap(ref arr[i + 1], ref arr[i]);
                isSwaped = true;
            }
        }
    } while (isSwaped);
}

public static void Swap<T>(ref T a, ref T b) where T : IComparable<T>
{
    var tmp = a;
    a = b;
    b = tmp;
}