奇偶転置ソート

奇偶転置ソート（きぐうてんちソート、）は、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。
バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n2)である。
組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。
そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (n-1) ステップで処理が完了する。
ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。
アルゴリズム.
奇偶置換ソートは、奇数番目とその次の偶数番目を組 (組1) にして比較／交換した後、偶数番目とその次の奇数番目を組 (組2) にして比較／交換することを繰り返すアルゴリズムである。
これを繰り返す。
実装例.
1番目の位置を表す添字が 0 になっているのはC言語の仕様である。
double data[N] = {値1, 値2, 値3, ..., 値N} ;
bool changed ;
do
 changed = false ;
 for (int i=0 ; i<N-1 ; i+=2)　/* 組1 */
 if (data[i] > data[i+1])
 swap (&data[i], &data[i+1]) ;
 changed = true ;
 for (int i=1 ; i<N-1 ; i+=2) /* 組2 */
 if (data[i] > data[i+1])
 swap (&data[i], &data[i+1]) ;
 changed = true ;
 while (changed) ;
動作例.
formula_1 のような表記は比較されるデータの組を示す。
初期データ: formula_2
交換回数:formula_3（バブルソートと同じ）