循環ソート

循環ソート

ランダムな数字のリストをソートするサイクルソートの例。
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	Θ( n2 ) ...
最高の パフォーマンス	Θ( n2 ) ...
平均的 なパフォーマンス	Θ( n2 ) ...
最悪の場合の 空間複雑度	合計Θ( n )、補助Θ( 1 )
最適	いいえ

サイクル ソートは、インプレースで不安定な ソート アルゴリズムであり、他のインプレース ソート アルゴリズムとは異なり、元の配列への書き込みの合計回数に関して理論的に最適な比較ソートです。これは、ソートする順列をサイクルに分解し、サイクルを個別に回転させてソート結果を得ることができるという考えに基づいています。

他のほとんどのソートとは異なり、アイテムは、アクションの邪魔にならないようにするためだけに配列内の他の場所に書き込まれることはありません。各値は、すでに正しい位置にある場合は 0 回書き込まれ、正しい位置に 1 回書き込まれます。これは、完了したインプレース ソートに必要な上書きの最小回数と一致します。

書き込み回数を最小限に抑えることは、書き込みのたびにメモリの寿命が短くなるフラッシュメモリなどのEEPROMなど、巨大なデータセットへの書き込みに非常にコストがかかる場合に有効です。^{[引用が必要]}

循環ソートの考え方を説明するために、異なる要素を持つリストを考えてみましょう。要素 が与えられた場合、リスト全体の中で より小さい要素の数を数えるだけで、ソートされたリスト内でその要素が出現するインデックスを見つけることができます。 ${\displaystyle x}$${\displaystyle x}$

1. 要素がすでに正しい位置にある場合は何もしません。
2. そうでない場合は、意図した位置に書き込みます。その位置には別の要素 が存在するため、それを正しい位置に移動する必要があります。要素を正しい位置に移動するこのプロセスは、要素が の元の位置に移動されるまで続きます。これでサイクルが完了します。${\displaystyle y}$${\displaystyle x}$

すべての要素に対してこのプロセスを繰り返すと、要素がまだ正しい位置にない場合に限り、1 回の書き込み操作でリストがソートされます。正しい位置を計算するには各要素ごとに時間がかかるため、2 次時間アルゴリズムになりますが、書き込み操作の数は最小限に抑えられます。 ${\displaystyle O(n)}$

上記の概要から実用的な実装を作成するには、次の 2 つの問題に対処する必要があります。

1. 正しい位置を計算するときは、サイクルの最初の要素を二重にカウントしないようにする必要があります。
2. 重複する要素が存在する場合、要素を正しい位置に移動しようとすると、その位置にすでに が存在する可能性があります。これらを単純に交換すると、アルゴリズムが無限に循環することになります。代わりに、重複する の後に要素を挿入する必要があります。${\displaystyle x}$${\displaystyle x}$

次のPython実装^{[1] [循環参照]}は、配列に対して循環ソートを実行し、ソートに必要な配列への書き込み回数をカウントします。

パイソン

def  cycle_sort (配列)  ->  int :
    """配列をその場でソートし、書き込み回数を返します。"""
    書き込み =  0

    # 配列をループして回転するサイクルを見つけます。
    # 最初の n-1 サイクルの後に、最後の項目がすでにソートされていることに注意してください。
     cycle_startが 範囲( 0 、len ( array ) - 1 )の 場合:   
        項目 = 配列[ cycle_start ]

        # アイテムを置く場所を見つけます。
        位置 = サイクル開始
         i が 範囲( cycle_start + 1 、len (配列) )内に ある場合:   
             配列[ i ]  < 項目の場合:
                位置 +=  1

        # アイテムがすでに存在する場合、これはサイクルではありません。
         pos  ==  cycle_startの場合:
            続く

        # それ以外の場合は、アイテムをそこに、または重複したアイテムの直後に配置します。
         項目 == 配列[位置]の場合:
            位置 +=  1

        配列[位置]、 項目 = 項目、 配列[位置]
        書き込み +=  1

        # サイクルの残りを回転させます。
         pos  !=  cycle_startの場合:
            # アイテムを置く場所を見つけます。
            位置 = サイクル開始
             i が 範囲( cycle_start + 1 、len (配列) )内に ある場合:   
                 配列[ i ]  < 項目の場合:
                    位置 +=  1

            # 重複するアイテムがある場合は、そのアイテムをその場所または直後に配置します。
             項目 == 配列[位置]の場合:
                位置 +=  1
            配列[位置]、 項目 = 項目、 配列[位置]
            書き込み +=  1

    リターン 書き込み

C++で記述された次の実装は、単純に循環配列ソートを実行します。

テンプレート<型名型配列>  
void cycle_sort ( type_array *配列、int array_size )    
{
	( int cycle_start = 0 ; cycle_start < array_size - 1 ; cycle_start ++ )の場合          
	{
		type_array item =配列[ cycle_start ];   

		位置= cycle_start ;​   
		( 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 )   
		{
			位置=サイクル開始;  
			( int i = cycle_start + 1 ; i < array_size ; i ++ )の場合          
				if (配列[ i ] <項目)   
					位置+= 1 ;  
			while (項目==配列[位置])   
				位置+= 1 ;  

			std :: swap (配列[ pos ],項目); 
		}
	}
}

配列に比較的少数の項目の重複のみが含まれている場合、定数時間の 完全ハッシュ関数を使用すると、項目¹を配置する場所の検索が大幅に高速化され、並べ替えが Θ( n ² ) 時間から Θ( n + k ) 時間になります ( kはハッシュの合計数)。配列はハッシュの順序で並べ替えられるため、正しい順序付けを行うハッシュ関数を選択することが重要です。

ソートの前に、ハッシュでソートされたヒストグラムを作成し、配列内の各ハッシュの出現回数をカウントします。次に、ヒストグラムの各エントリの累積合計を含むテーブルを作成します。累積合計テーブルには、配列内の各要素の位置が含まれます。要素の適切な場所は、線形検索ではなく、定数時間のハッシュと累積合計テーブル検索によって見つけることができます。

^ 「サイクルソート：線形ソート法」、コンピュータジャーナル（1990）33（4）：365-367。

• 制限のないバリアントの元のソース
• Cyclesort - ちょっと面白いソートアルゴリズム