奇偶転置ソート

奇偶転置ソート

奇偶転置ソートによるランダムな数字のリストのソートの例
クラス	ソート
データ構造	配列
最悪計算時間	${\displaystyle O(n^{2})}$
最良計算時間	${\displaystyle O(n)}$
最悪空間計算量	${\displaystyle O(1)}$

奇偶転置ソート（きぐうてんちソート、英: odd-even sort）は、ソートのアルゴリズムの一つで、バブルソートを改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。

バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n²)である。

組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (n-1) ステップで処理が完了する。 ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。

アルゴリズム

奇偶置換ソートは、奇数番目とその次の偶数番目を組 (組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) ;

動作例

${\displaystyle {\widehat {8,4}}}$ のような表記は比較されるデータの組を示す。

初期データ: ${\displaystyle 8,4,3,7,6,5,2,1}$

時間	置換前の状態	組	置換個数	置換後の状態
1	${\displaystyle {\widehat {8,4}},{\widehat {3,7}},{\widehat {6,5}},{\widehat {2,1}}}$	組1	3	${\displaystyle 4,8,3,7,5,6,1,2}$
2	${\displaystyle 4,{\widehat {8,3}},{\widehat {7,5}},{\widehat {6,1}},2}$	組2	3	${\displaystyle 4,3,8,5,7,1,6,2}$
3	${\displaystyle {\widehat {4,3}},{\widehat {8,5}},{\widehat {7,1}},{\widehat {6,2}}}$	組1	4	${\displaystyle 3,4,5,8,1,7,2,6}$
4	${\displaystyle 3,{\widehat {4,5}},{\widehat {8,1}},{\widehat {7,2}},6}$	組2	2	${\displaystyle 3,4,5,1,8,2,7,6}$
5	${\displaystyle {\widehat {3,4}},{\widehat {5,1}},{\widehat {8,2}},{\widehat {7,6}}}$	組1	3	${\displaystyle 3,4,1,5,2,8,6,7}$
6	${\displaystyle 3,{\widehat {4,1}},{\widehat {5,2}},{\widehat {8,6}},7}$	組2	3	${\displaystyle 3,1,4,2,5,6,8,7}$
7	${\displaystyle {\widehat {3,1}},{\widehat {4,2}},{\widehat {5,6}},{\widehat {8,7}}}$	組1	3	${\displaystyle 1,3,2,4,5,6,7,8}$
8	${\displaystyle 1,{\widehat {3,2}},{\widehat {4,5}},{\widehat {6,7}},8}$	組2	1	${\displaystyle 1,2,3,4,5,6,7,8}$

交換回数:${\displaystyle 3+3+4+2+3+3+3+1=22}$（バブルソートと同じ）

外部リンク

• Odd-even Transposition Sort

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート
カテゴリ