奇偶転置ソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search
奇偶転置ソート
Example of odd-even transposition sort sorting a list of random numbers.
奇偶転置ソートによるランダムな数字のリストのソートの例
クラス ソート
データ構造 配列
最悪計算時間
最良計算時間
最悪空間計算量

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

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

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

動作例[編集]

のような表記は比較されるデータの組を示す。

初期データ:

時間 置換前の状態 置換個数 置換後の状態
1 組1 3
2 組2 3
3 組1 4
4 組2 2
5 組1 3
6 組2 3
7 組1 3
8 組2 1

交換回数:バブルソートと同じ)

外部リンク[編集]