奇偶転置ソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[File:Odd even sort animation.gif|Example of odd-even transposition sort sorting a list of random numbers.]]
|caption=奇偶転置ソートによるランダムな数字のリストのソートの例
|data=[[配列]]
|time=<math>O(n^2)</math>
|best-time=<math>O(n)</math>
|space= <math>O(1)</math>
|optimal=No
}}

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

バブルソートと同じく[[安定ソート|安定]]な内部ソートで、最悪の場合で[[計算複雑性理論|時間計算量]]は[[ランダウの記号|O]](n<sup>2</sup>)である。

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

== アルゴリズム ==
奇偶置換ソートは、[[奇数]]番目とその次の[[偶数]]番目を組 (組1) にして比較／交換した後、偶数番目とその次の奇数番目を組 (組2) にして比較／交換することを繰り返すアルゴリズムである。

;組1:（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後に
;組2:（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。

これを繰り返す。

=== 実装例 ===
1番目の位置を表す添字が 0 になっているのは[[C言語]]の仕様である。
<syntaxhighlight lang="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) ;
</syntaxhighlight>

=== 動作例 ===
<math>\widehat{8,4}</math> のような表記は比較されるデータの組を示す。

初期データ: <math>8,4,3,7,6,5,2,1</math>

{|class=wikitable
!時間!!置換前の状態!!組!!置換個数!!置換後の状態
|-
|style="text-align:right"|1
|<math>\widehat{8,4}, \widehat{3,7}, \widehat{6,5}, \widehat{2,1}</math>
|組1
|style="text-align:right"|3
|<math>4,8,3,7,5,6,1,2</math>
|-
|style="text-align:right"|2
|<math>4,\widehat{8,3},\widehat{7,5},\widehat{6,1},2</math>
|組2
|style="text-align:right"|3
|<math>4,3,8,5,7,1,6,2</math>
|-
|style="text-align:right"|3
|<math>\widehat{4,3},\widehat{8,5},\widehat{7,1},\widehat{6,2}</math>
|組1
|style="text-align:right"|4
|<math>3,4,5,8,1,7,2,6</math>
|-
|style="text-align:right"|4
|<math>3,\widehat{4,5},\widehat{8,1},\widehat{7,2},6</math>
|組2
|style="text-align:right"|2
|<math>3,4,5,1,8,2,7,6</math>
|-
|style="text-align:right"|5
|<math>\widehat{3,4},\widehat{5,1},\widehat{8,2},\widehat{7,6}</math>
|組1
|style="text-align:right"|3
|<math>3,4,1,5,2,8,6,7</math>
|-
|style="text-align:right"|6
|<math>3,\widehat{4,1},\widehat{5,2},\widehat{8,6},7</math>
|組2
|style="text-align:right"|3
|<math>3,1,4,2,5,6,8,7</math>
|-
|style="text-align:right"|7
|<math>\widehat{3,1}, \widehat{4,2}, \widehat{5,6}, \widehat{8,7}</math>
|組1
|style="text-align:right"|3
|<math>1,3,2,4,5,6,7,8</math>
|-
|style="text-align:right"|8
|<math>1,\widehat{3,2},\widehat{4,5},\widehat{6,7},8</math>
|組2
|style="text-align:right"|1
|<math>1,2,3,4,5,6,7,8</math>
|}

交換回数:<math>3+3+4+2+3+3+3+1=22</math>（[[バブルソート]]と同じ）

== 外部リンク ==
* [http://www.cs.mu.oz.au/498/notes/node34.html Odd-even Transposition Sort]

{{ソート}}
{{Computer-stub}}

{{DEFAULTSORT:きくうてんちそおと}}
[[Category:ソート]]