循環ソート
 ランダムな数字のリストをソートするサイクルソートの例。 | |
| クラス | ソートアルゴリズム |
|---|---|
| データ構造 | 配列 |
| 最悪の場合の パフォーマンス | Θ( n 2 ) |
| 最高の パフォーマンス | Θ( n 2 ) |
| 平均的な パフォーマンス | Θ( n 2 ) |
| 最悪の場合の 空間複雑度 | 合計Θ( n )、補助Θ( 1 ) |
| 最適 | はい、元のアレイへの書き込み総数に関しては |
循環ソートは、インプレース型の不安定 ソートアルゴリズムであり、他のインプレースソートアルゴリズムとは異なり、元の配列への書き込み回数の点で理論的に最適な比較ソートです。これは、ソート対象となる順列を循環に分解し、循環を個別に回転させることによってソート結果を得ることができるという考えに基づいています。
他のほぼすべてのソートとは異なり、アイテムは単にアクションの邪魔にならないようにするためだけに配列内の他の場所に書き込まれることはありません。各値は、既に正しい位置にある場合は0回書き込まれ、正しい位置に1回書き込まれます。これは、インプレースソートを完了するために必要な最小限の上書き回数と一致します。
書き込み回数を最小限に抑えることは、書き込みのたびにメモリの寿命が短くなるフラッシュメモリなどの EEPROM など、巨大なデータセットへの書き込みに非常にコストがかかる場合に有効です。 [要出典]
アルゴリズム
循環ソートの考え方を説明するために、異なる要素を持つリストを考えてみましょう。要素 が与えられた場合、リスト全体の中で より小さい要素の数を数えるだけで、ソート後のリストにおいてその要素が出現するインデックスを見つけることができます。
- 要素がすでに正しい位置にある場合は何もしません。
- そうでない場合は、意図した位置に書き込みます。その位置には別の要素 が存在するため、これを正しい位置に移動する必要があります。要素を正しい位置に移動するこのプロセスは、要素が の元の位置に移動されるまで続きます。これでサイクルが完了します。
このプロセスをすべての要素に対して繰り返すことで、リストはソートされます。要素が既に正しい位置にない場合のみ、書き込み操作は1回のみ行われます。正しい位置を計算するには各要素ごとに時間がかかるため、結果として2乗時間アルゴリズムとなりますが、書き込み操作の回数は最小限に抑えられます。
実装
上記の概要から実用的な実装を作成するには、次の 2 つの問題に対処する必要があります。
- 正しい位置を計算するときは、サイクルの最初の要素を二重にカウントしないように注意する必要があります。
- 重複する要素が存在する場合、要素を正しい位置に移動しようとした際に、その位置に既に が存在する可能性があります。これらを単純に入れ替えると、アルゴリズムが無限に循環してしまいます。そのため、重複する の後にを挿入する必要があります。
次のPython実装[1] [循環参照]は配列に対して循環ソートを実行し、ソートに必要な配列への書き込み回数をカウントします。
def cycle_sort (配列) -> int : 「配列をその場でソートし、書き込み回数を返します。」 書き込み = 0 # 配列をループして回転するサイクルを見つけます。 # 最初の n-1 サイクルの後に、最後の項目はすでにソートされていることに注意してください。 cycle_start が 範囲( 0 、 len (配列) - 1 )の場合: アイテム = 配列[ cycle_start ] # アイテムを置く場所を見つけます。 pos = サイクル開始 iが 範囲( cycle_start + 1 、len (配列) )の 場合: 配列[ i ] < 項目の場合: 正 += 1 # アイテムがすでに存在する場合、これはサイクルではありません。 pos == cycle_start の場合: 続く # それ以外の場合は、重複する項目をその場所または直後に配置します。 項目 == 配列[位置]の場合: 正 += 1 配列[位置], 項目 = 項目, 配列[位置] 書き込み += 1 # サイクルの残りを回転させます。 pos != cycle_startの場合: # アイテムを置く場所を見つけます。 pos = サイクル開始 iが 範囲( cycle_start + 1 、len (配列) )の 場合: 配列[ i ] < 項目の場合: 正 += 1 # 重複するアイテムがある場合は、そのアイテムをその場所または直後に配置します。 項目 == 配列[位置]の場合: 正 += 1 配列[位置], 項目 = 項目, 配列[位置] 書き込み += 1 戻り 書き込みC++で記述された次の実装は、単純に循環配列ソートを実行します。
テンプレート<型名 型配列> void cycle_sort ( type_array *配列, int array_size ) {for ( int cycle_start = 0 ; cycle_start < array_size - 1 ; cycle_start ++ ) {type_array item =配列[ cycle_start ]; int pos = cycle_start ; for ( int i = cycle_start + 1 ; i < array_size ; i ++ ) if (配列[ i ] <項目) 正+= 1 ; if ( pos == cycle_start ) 続く;while (項目==配列[位置]) 正+= 1 ; std :: swap (配列[ pos ],項目); while ( pos != cycle_start ) {pos =サイクル開始; for ( int i = cycle_start + 1 ; i < array_size ; i ++ ) if (配列[ i ] <項目) 正+= 1 ; while (項目==配列[位置]) 正+= 1 ; std :: swap (配列[ pos ],項目); }}}状況に応じた最適化
配列に含まれる項目の重複が比較的少数の場合、定数時間の 完全ハッシュ関数は、項目1の配置場所の検索を大幅に高速化します。これにより、ソート処理はΘ( n 2 )時間からΘ( n + k )時間に短縮されます（ kはハッシュの総数）。配列はハッシュの順序でソートされるため、適切な順序付けを行うハッシュ関数を選択することが重要です。
ソートの前に、ハッシュでソートされたヒストグラムを作成し、配列内の各ハッシュの出現回数を数えます。次に、ヒストグラムの各エントリの累積合計を含むテーブルを作成します。累積合計テーブルには、各要素の配列内の位置が含まれます。要素の適切な位置は、線形探索ではなく、定数時間のハッシュと累積合計テーブル検索によって見つけることができます。
参考文献
- ^ sr:Ciklično sortiranje#Algoritam
外部リンク
^ 「サイクルソート：線形ソート法」、コンピュータジャーナル（1990）33（4）：365-367。
- 無制限バリアントのオリジナルソース
- Cyclesort - ちょっとした興味深いソートアルゴリズム
