[アルゴリズム]カウントソートカウントSort

    各数値の数をカウントして保存し、ソートします.

比較ソートの制限はO(nlogn)
=>カウントソートはnon-combination sortでこの制限を超えることができます.

安定ソート(安定)

の最大値は一時的な配列の大きさとなるため、数字の大きさの影響が大きい.(与えられた数字によっては、効率が低下する可能性があります)

1.a.ソートする配列(データ)の最大値をサイズとする一時配列(カウント)を作成します.
b.各要素を巡回し、その値を一時配列に格納する.
c.出場回数を累積加算する.
2.a.dataを後ろから前に巡視してtempに入れます.1 cから求めた積算和(count[i])は数字の位置を表す.
b.count[i]の値を1つ減らします.
この過程を繰り返す.

コード

#include <iostream>

using namespace std;
int arr[1000] = { 10,23,1,1,23,23,4,5,6,7 };
int a[1000];
void counting_sort(int list[])
{
	int temp[1000];
	int count[1000];
	memset(temp, 0, sizeof(temp));
	//더해주기
	for (int i = 0; i < 10; i++)
		temp[list[i]]++;
	count[0] = temp[0];
	//누적으로 더해주기
	for (int i = 1; i <= 23; i++)
		count[i] = count[i - 1] + temp[i];
	//더해졌는지 확인
	for (int i = 0; i <= 23; i++)
		cout << count[i] << " ";
	cout << endl;
	//제일 끝에서 부터 삽입
	for (int i = 9; i >= 0; i--)
	{
		a[  count[ list[i] ]-1 ] = list[i];
		count[list[i]]--;
		//들어가는 위치 보기
		for (int j = 0; j < 10; j++)
			cout << a[j] << " ";
		cout << endl;
	}
	//정렬된 행렬
	for (int i = 0; i < 10; i++)
		cout << a[i] << " ";
	cout << endl;
}
int main()
{
	counting_sort(arr);
}

時間の複雑さ
n:データカウント、k:範囲(最大値)
時間複雑度最適Ω(n+k)平均値Θ(n+k)ワーストO(n+k)
=>kがnより小さい数はO(n)であってもよいが、kがnより大きい数はO(無限)であってもよい.例えば、10個の数字を並べ替えた場合、最大の数字が1000の場合、O(n^3)となる

スペースの複雑さ:O(k)

注：リンク1
メモリンク2
注：リンク3