奇偶転置ソート（きぐうてんちソート、）は、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。
バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n2)である。
組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、高々 n ステップでソートが完了する。 ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。
アルゴリズム 奇偶置換ソートは、奇数番目とその次の偶数番目を組 (組1) にして比較／交換した後、偶数番目とその次の奇数番目を組 (組2) にして比較／交換することを繰り返すアルゴリズムである。
組1（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後に 組2（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。
これを繰り返す。
実装例 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) ;
動作例 のような表記は比較されるデータの組を示す。
初期データ:
時間置換前の状態組置換個数置換後の状態1組132組233組144組225組136組237組138組21
交換回数:（バブルソートと同じ）
出典
外部リンク Odd-even Transposition Sort