奇偶転置ソート

奇偶転置ソート

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

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

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

組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (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