奇偶転置ソート

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

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

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

ペアの比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。

アルゴリズム[編集]

奇偶置換ソートは、奇数番目とその次の偶数番目をペア (Pair1) にして比較/交換した後、偶数番目とその次の奇数番目をペア (Pair2) にして比較/交換することを繰り返すアルゴリズムである。

Pair1:(1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…)の後に

Pair2:(2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…)を行う。これを繰り返す。

実装例[編集]

1番目が i=0 になっているのはC言語の仕様。

 int data[N] = { /* ... */ };
 int flag = 1;
 int i;
 
 while(flag) {
   flag = 0;
   for (i = 0; i < N-1; i += 2) { /* Pair1 */
     if (data[i] > data[i+1]) {
       swap(&data[i], &data[i+1]);
       flag = 1;
     }
   }
   for (i = 1;i < N-1;i += 2) { /* Pair2 */
     if (data[i] > data[i+1]) {
       swap(&data[i], &data[i+1]);
       flag = 1;
     }
   }
 }

動作例[編集]

下線は比較(と交換)されたデータのペアを示す。

初期データ: 8 4 3 7 6 5 2 1

8 4 3 7 6 5 2 1
1回目のスキャン終了後:(Pair1/交換回数:3)
4 8 3 7 5 6 1 2

4 8 3 7 5 6 1 2
2回目のスキャン終了後:(Pair2/交換回数:3)
4 3 8 5 7 1 6 2

4 3 8 5 7 1 6 2
3回目のスキャン終了後:(Pair1/交換回数:4)
3 4 5 8 1 7 2 6

3 4 5 8 1 7 2 6
4回目のスキャン終了後:(Pair2/交換回数:2)
3 4 5 1 8 2 7 6

3 4 5 1 8 2 7 6
5回目のスキャン終了後:(Pair1/交換回数:3)
3 4 1 5 2 8 6 7

3 4 1 5 2 8 6 7
6回目のスキャン終了後:(Pair2/交換回数:3)
3 1 4 2 5 6 8 7

3 1 4 2 5 6 8 7
7回目のスキャン終了後:(Pair1/交換回数:3)
1 3 2 4 5 6 7 8

1 3 2 4 5 6 7 8
8回目のスキャン終了後:(Pair2/交換回数:1)
1 2 3 4 5 6 7 8

交換回数:3+3+4+2+3+3+3+1=22(バブルソートと同じ)

外部リンク[編集]