ソートアルゴリズムまとめ(一)カウントソート

比較ソートアルゴリズムの時間複雑度の下限はO(nlogn)であり,ここでは非比較ソートアルゴリズムを紹介する:カウントソート,その時間複雑度はO(n)である.
 
カウントソートの原理
 
3つの配列があると仮定し,A,B,C,Aはソート対象配列,Bは出力配列,Cは一時配列である.
 
カウントソートの考え方は、Aの各要素xについてx要素の個数n以下を決定し、一時配列Cに保存することであり、これにより、一時配列Cを検索することで、ソート対象配列の各要素の位置を直接決定することができ、比較を回避することができる.
 
配列Aは、以下のデータを保持するものとする
3
1
3
5
4
0
 
1個の数が0以下、2個の数が1以下、4個の数が3以下、5個の数が4以下、6個の数が5以下であることが決定され、配列Cが得られる
1
2
4
5
6
 
このように明らかに0は0番の位置に置くべきで、1は1番の位置に並べて、1番目の3は3番の位置に並べてからC[3]は減少して、2番目の3は2番の位置に並べて、順番に類推して、最終的に並べ替えを完成します.
 
参照コード:

#include 
#include 
using namespace std;

int Counter_Sort(int *input,int *output,int length,int type);

void main()
{
	int i;
	int a[]={9,8,7,6,5,4,3,2,1,22,67,11,5,3,99,102,54};
	int b[17];
	if (Counter_Sort(a,b,17,0) == 0)
	{
		for (i=0;i<17;i++)
		{
			cout < 1024)
	{
		return -1;
	}
	for (i=0;i<1024;i++)
	{
		tmp[i]=0;
	}
	for (i=0;i=0;i--)       
	{
		if (0 == type)		//  
		{
			output[tmp[input[i]]-1]=input[i];
			tmp[input[i]]--;
		}
		else if (1 == type) //  
		{
			output[length-tmp[input[i]]]=input[i];
			tmp[input[i]]--;
		}
		else
		{
			return -3;
		}
	}
	return 0;
}

tmp[s[i]]要素の個数を決定する際にO(n)時間を消費し、ある要素の個数よりもO(n)時間を消費することを決定し、要素の最終位置がO(n)時間を消費することを決定し、やっと時間の複雑度がO(n)であり、補助空間がmax(s[i])、すなわちO(n)である必要がある
カウントソートが安定しているかどうかについて:前文で与えられたカウントソートコードは安定していない.3,3,3があると仮定すると、前文のコードは最初の3を最後の3の位置に置く.
ループ変数を少し変更すると、カウントソートが安定し、コードの53行目を次のように変更できます.

for (i=length-1;i>=0;i--)

修正後は後から付与され、3番目の3番目は3番目の3番目の位置に肯定的に配置されます.