|
奇偶転置ソート（きぐうてんちソート、）は、ソートのアルゴリズムの一つで、バブルソートを、改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートではペアごとに行う。 バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。 ペアの比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 == アルゴリズム == 奇偶置換ソートは、奇数番目とその次の偶数番目をペア (Pair1) にして比較／交換した後、偶数番目とその次の奇数番目をペア (Pair2) にして比較／交換することを繰り返すアルゴリズムである。 Pair1:（1番目と2番目を比較、3番目と4番目を比較、5番目と6番目を比較、…）の後に Pair2:（2番目と3番目を比較、4番目と5番目を比較、6番目と7番目を比較、…）を行う。これを繰り返す。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「奇偶転置ソート」の詳細全文を読む スポンサード リンク
|