奇偶転置ソート
奇偶転置ソートによるランダムな数字のリストのソートの例 | |
クラス | ソート |
---|---|
データ構造 | 配列 |
最悪計算時間 | |
最良計算時間 | |
最悪空間計算量 |
奇偶転置ソート(きぐうてんちソート、英: 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 |
交換回数:(バブルソートと同じ)
外部リンク
- Odd-even Transposition Sort
| |
---|---|
理論 |
|
交換ソート | |
選択ソート | |
挿入ソート | |
マージソート |
|
非比較ソート | |
並行ソート | |
混成ソート | |
その他 | |
非効率的/ ユーモラスソート | |
カテゴリ |
- 表示
- 編集