奇遇転置ソートとは
奇遇転置ソートとは、交換ソートの一種であり、バブルソートの改良版ソートアルゴリズムです。隣り合った要素同士を順次交換するバブルソートと異なり、要素番号が奇数偶数のペア同士で交換を行います。
ソートの特性としてはバブルソートと同じく、安定 な 内部 ソートです。計算量も 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;
}