[Algorithm] Counting Sort

💡 動作原理

この文章では、カウントソートについて説明します.カウントソートの原理は、要素値の個数を計算し、新しい配列の個数に基づいて位置を設定することです.

新しい配列を宣言し、ソートする配列の要素を計算して格納します.新しく並んだ名前はCountと言いますね.Countのインデックス値はソートする配列の要素値であり、Countのデータ値はインデックス値の個数である.たとえば、ソートする配列に3という要素が5つある場合、count[3]=5です.i=0からi=N-1の間を1回ナビゲートするだけで、上図のようにCount配列を埋め込むことができます.
Output配列を宣言し、既存の配列をソートします.Outputを正しくソートするために、Countの値をCountのインデックスに変換すると、Outputの最大インデックスに入ることができます.これにより、Countの値を自分より前の要素の和に変換することができます.Count[i]=Count[i]+Count[i-1]点化式を使用します.
やっとOutput配列を埋めることができました.これで、ソートする配列を再参照し、Countを参照してOutput配列に要素を順次入力できます.要素をOutput配列に入れるたびにCountの値は-1となり、Output配列が完了するとCountの値はCountのインデックスがOutputに入る最小インデックスとなる.これがCounting Sort(カウントソート)です.

💻 コード#コード#

void Counting_Sort(){
	for (int i = 0; i < N; i++) Count[Arr[i]]++;
	for (int i = 1; i <= Max; i++) Count[i] = Count[i] + Count[i - 1];
	for (int i = 0; i < N; i++){
		Count[Arr[i]]--;
		Output[Count[Arr[i]]] = Arr[i];
	}
}

時間の複雑さ

Counting Sort(カウントソート)の時間的複雑度は他のソートとは異なり,他のエレメントと比較して交換する方式でソートするのではなく,エレメントの個数を計算することで自然にソートするアルゴリズムであるため,時間的複雑度はO(N)O(N)O(N)N(N)N)である.
ただし、ソートするデータ値の最大値の配列を宣言する必要があります.したがって、データ値の範囲が大きいほど、スペースの複雑さが大きくなり、実行速度が遅くなります.したがって、Counting Sort(カウントソート)を使用するには、データ値の範囲を決定する必要があります.
O(N)O(N)O(N)