カウントソート

カウントソート

クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n+k)}$ここで、k は負でないキー値の範囲です。
最悪の場合の 空間複雑度	${\displaystyle O(n+k)}$

コンピュータサイエンスにおいて、カウンティングソートは、小さな正の整数であるキーに従ってオブジェクトのコレクションをソートするアルゴリズムです。つまり、整数ソートアルゴリズムです。これは、異なるキー値を持つオブジェクトの数をカウントし、それらのカウントにプレフィックス合計を適用して、出力シーケンス内の各キー値の位置を決定することによって機能します。実行時間は、アイテムの数と最大キー値と最小キー値の差に比例するため、キーの変動がアイテムの数よりも大幅に大きくない状況でのみ直接使用するのに適しています。これは、より大きなキーをより効率的に処理できる別のソートアルゴリズムである基数ソートのサブルーチンとしてよく使用されます。 ^{[1] [2] [3]}

カウンティングソートは比較ソートではありません。キー値を配列のインデックスとして使用し、比較ソートのΩ ( n log n ) 下限は適用されません。^[1] バケットソートはカウンティングソートの代わりに使用でき、同様の時間分析が必要です。ただし、カウンティングソートと比較すると、バケットソートでは各バケット内のアイテムセットを保持するためにリンクリスト、動的配列、または事前に割り当てられた大量のメモリが必要ですが、カウンティングソートではバケットごとに1つの数値 (アイテムの数) が格納されます。^[4]

最も一般的なケースでは、カウンティングソートへの入力はn 個の項目のコレクションで構成され、各項目には最大値が最大でkである非負の整数キーがあります。^[3] カウンティングソートのいくつかの説明では、ソートする入力はより単純な整数のシーケンスであると想定されていますが、^[1]この単純化はカウンティングソートの多くのアプリケーションに対応していません。たとえば、基数ソートのサブルーチンとして使用される場合、カウンティングソートの各呼び出しのキーは、より大きな項目キーの個々の数字です。項目から分離されたキーの数字のソートされたリストのみを返すだけでは不十分です。

基数ソートなどのアプリケーションでは、最大キー値kの境界は事前にわかっており、アルゴリズムへの入力の一部であると想定できます。ただし、kの値がまだわかっていない場合は、最初のステップとして、データに対して追加のループを実行して最大キー値を決定することで計算できます。

出力はキー順に並べられた要素の配列です。基数ソートに適用するため、カウンティングソートは安定したソートでなければなりません。つまり、2つの要素が同じキーを共有する場合、出力配列内の相対的な順序と入力配列内の相対的な順序が一致する必要があります。^{[1] [2]}

疑似コードでは、アルゴリズムは次のように表現されます。

関数CountingSort(入力, k )
    count ← k + 1 個のゼロ
    の配列
    出力 ← 入力と同じ長さの配列
    
     i = 0からlength(input) - 1まで、 j = key(input[ i ])を実行します。
        
        カウント[ j ] = カウント[ j ] + 1

     i = 1から k まで
        count[ i ] = count[ i ] + count[ i - 1]を実行します。

     i = length(input) - 1から0まで、j = key(input[ i ])を実行します。
        
        カウント[ j ] = カウント[ j ] - 1
        出力[count[ j ]] = 入力[ i ]

    出力を
返す

ここでinputは、ソートする入力配列、key入力配列内の各項目の数値キーを返します。countは、最初に各キーの項目の数を格納するために使用され、次に (2 番目のループの後に) 各キーの項目を配置する位置を格納するために使用される補助配列 k、は非負のキー値の最大値、はoutputソートされた出力配列です。

要約すると、アルゴリズムは最初のループでアイテムをループし、コレクション内で各キーが出現する回数のヒストグラムinputを計算します。その後、2 番目のループで、 のプレフィックス合計計算を実行してcount、各キーについて、そのキーを持つアイテムを配置する位置の範囲を決定します。つまり、キーのアイテムは位置 から配置されます。最後に、3 番目のループで、 のアイテムを再度ループしますが、逆の順序で、各アイテムを配列内のソートされた位置に移動します。^{[1] [2] [3]}${\displaystyle i}$count[${\displaystyle i}$]inputoutput

ここでは、同じキーを持つ項目の相対的な順序が保持されます。つまり、これは安定したソートです。

このアルゴリズムはfor、再帰やサブルーチン呼び出しのない単純なループのみを使用するため、解析は簡単です。カウント配列の初期化と、カウント配列に対してプレフィックス合計を実行する 2 番目の for ループは、それぞれ最大k + 1回反復されるため、O ( k )時間がかかります。他の 2 つの for ループと出力配列の初期化は、それぞれO ( n )時間がかかります。したがって、アルゴリズム全体の時間は、これらのステップの時間の合計、O ( n + k )になります。^{[1] [2]}

長さk + 1とnの配列を使用するため、アルゴリズムの総スペース使用量もO ( n + k )です。^{[1]最大キー値が項目数よりも大幅に小さい問題インスタンスの場合、カウンティングソートは、入力配列と出力配列以外の唯一のストレージがスペース}O ( k )を使用する Count 配列であるため、スペース効率が非常に高くなります。^[5]

ソートする各項目自体が整数であり、キーとしても使用される場合、カウントソートの 2 番目と 3 番目のループを組み合わせることができます。2 番目のループでは、キーを持つ項目をi出力に配置する位置を計算する代わりに、Count[i]数値のコピーをi出力に追加するだけです。

このアルゴリズムは、入力に存在するキーの場合は を、存在しないキーの場合はを格納するビット ベクトルCountで配列を置き換えることにより、重複キーを削除するためにも使用できます。さらに、項目自体が整数キーである場合は、2 番目と 3 番目のループの両方を完全に省略でき、ビット ベクトル自体が出力として機能し、範囲の最小値に追加された非エントリのオフセットとして値を表します。したがって、このバリアントでは、ビット配列に配置するだけでキーが並べ替えられ、重複が削除されます。 onezerozero

最大キーサイズがデータ項目数よりも大幅に小さいデータの場合、入力をほぼ等しいサイズのサブ配列に分割し、各サブ配列を並列処理してサブ配列ごとに個別のカウント配列を生成し、カウント配列をマージすることで、カウンティングソートを並列化できます。並列基数ソートアルゴリズムの一部として使用する場合、キーサイズ（基数表現の基数）は、分割されたサブ配列のサイズと一致するように選択する必要があります。^[6]カウンティングソートアルゴリズムの単純さと、簡単に並列化できるプレフィックス合計プリミティブの使用により、より細粒度の並列アルゴリズムでも使用できます。^[7]

説明したように、カウンティングソートはインプレースアルゴリズムではありません。カウント配列を無視しても、別々の入力配列と出力配列が必要です。カウント配列のみを補助ストレージとして使用し、入力として与えられた同じ配列内でアイテムをソートされた順序に配置するようにアルゴリズムを変更することは可能ですが、変更されたインプレースバージョンのカウンティングソートは安定していません。^[3]

基数ソート自体ははるかに古い歴史を持つが、カウンティングソートとその基数ソートへの応用は、1954年にハロルド・H・スワードによって発明された。 ^{[1] [4] [8]}

Wikibookアルゴリズム実装には、次のトピックに関するページがあります:カウントソート

• カウントソート html5 視覚化
• カーディフ大学のデモンストレーション アプレット 2013-06-02 にWayback Machineでアーカイブされました
• Kagel, Art S. (2006 年 6 月 2 日)、「counting sort」、Black, Paul E. (ed.)、『Dictionary of Algorithms and Data Structures』、米国国立標準技術研究所、 2011 年 4 月 21 日取得。