計数ソート - 似非学問的な手記

バケットソートと呼ばれるものの一種。
……ってことでいいのかな？
正直、自分の持ってる資料とWikipediaの情報が食い違っててどう書いたらいいもんかと……
まあ細かいことはおいておいて。

線形時間ソートの一つ、計数ソート(Counting Sort)。
クイックソートみたいな比較によるソートは理論上O(nlogn)の計算量が必要らしく、線形時間O(n)でソートするのにはある程度入力に仮定を置かなければならんらしい。なんでもかんでもO(n)でソートできるわけではないと。

と、いっても。
今回のアルゴリズムはMIN以上MAX以下の整数値をソートする。
例えば会員番号とかならソートキーは整数値だし、割と汎用的かも？

アイデアは、まず各々の整数値の個数を数える。
この数をC(MIN)〜C(MAX)とする。
計算量はO(n)

すると、それぞれどの整数値が配列のどこに入るのかがわかる。
"MIN"が入るのは0番目からC(MIN)番目まで
"MIN+1"が入るのはC(MIN)+1番目からC(MIN+1)+C(MIN)番目まで
"MIN+2"が入るのはC(MIN+1)+C(MIN)+1番目からC(MIN+2)+C(MIN+1)+C(MIN)番目まで
…
だから、
C(i+1)=C(i+1)+C(i)
という計算をi=MIN..MAX-1までforループで繰り返せば、
"MIN"が入るのは0番目からC(MIN)番目まで
"MIN+1"が入るのはC(MIN)+1番目からC(MIN+1)番目まで
"MIN+2"が入るのはC(MIN+1)+1番目からC(MIN+2)番目まで
…
というように、「（整数iが入る区間）＝C(i-1)+1〜C(i)」となる。
計算量はO(MAX-MIN)

そこまでわかれば、後は配列をC()使って並べていくだけ。
次の図みたいにC(i-1)+1からC(i)までiが入ることになる。
アルゴリズムが具体的にやることは、
整数値がkの要素をC(k)番目に入れて、C(k)から1を引く。
これをforでサイズ分繰り返して終了。
計算量はO(n)

ただこれだと、ソート済み配列自体は別の場所に作られるから、
元の場所にコピーする。
計算量はO(n)
以上。
結局、(MIN-MAX)がO(n)以下なら、全体的な計算量もO(n)となる。

In Placeなソートじゃないし、
そうでなくてもメモリは多少食うのが難点だけど、
かなりシンプルな方法なんで、面白いかなあと。

コードは以下。

class CountingSort{
	//Element:ソートする要素（整数値）
	//Sorted:ソート済み配列一時格納用メモリ
	//min:ソート値の下界

	//max:ソート値の上界
	public static void Csort(int Element[  ],int min,int max){
		int range = max - min + 1;
		int size = Element.length;
		int Count[  ] = new int[ range ];
		int Sorted[  ] = new int[ size ];
		
		//Countを0初期化

		for(int i=0;i<range;i++){
			Count[ i ] = 0;
		}
		
		//Elementがnをいくつ含むかをCount[ n-min ]に格納

		for(int i=0;i<size;i++){
			Count[ Element[ i ] ]++;
		}
		
		//Count[ n-min ]に「n以下の値の数」を格納

		for(int i=1;i<range;i++){
			Count[ i ] += Count[ i-1 ];
		}
		
		//Countを用いてSortedに値を格納

		for(int i=size-1;i>=0;i--){
			Sorted[ Count[ Element[ i ] ]-1 ] = Element[ i ];
			Count[ Element[ i ] ]--;
		}
		
		//ElementにSortedを転写

		for(int i=0;i<size;i++){
			Element[ i ] = Sorted[ i ];
		}
	}
}

個人的にもすごく見づらいコードだと思ってたんでカラーリング。
うおお見やすい（俺的自己満足）。
なお、コード化する際はC(i)を配列で表すことになるんで、実際はMIN〜MAXに対応するC(i)をC(0)〜C(MAX-MIN)としています。まあ書いとくまでもないか。

で、とりあえず覚書のターンは終わり……
なのだが。

このソート、その場じゃやっぱり無理だろうか？
つまり、最後の転写をなくすことはできないか。
それだけが嫌に気になる。

そこで。
個人的に工夫してみたのがこのコード。
しかも格段に速い！

class CountingSortInPlace{
	//Element:ソートする要素（整数値）
	//min:ソート値の下界
	//max:ソート値の上界

	public static void CIsort(int Element[  ],int min,int max){
		int range = max - min + 1;
		int size = Element.length;
		int Count[  ] = new int[ range ];
		
		//Countを0初期化

		for(int i=0;i<range;i++){
			Count[ i ]=0;
		}
		
		//Elementがnをいくつ含むかをCount[ n-min ]に格納

		for(int i=0;i<size;i++){
			Count[ Element[ i ] ]++;
		}
		
		int k=size-1;
		for(int i=range-1;i>=0;i--){
			for(int j=0;j<Count[ i ];j++){
				Element[ k-- ]=i+min;
			}
		}
	}
}

はい、冗談です。サーセン。
確かにソートされた配列を出力はしますよ。
ですが、「ソートされたキーの列を出力するプログラム」であって、「ソートキーと一緒にオブジェクトごと安定にソートするプログラム」ではないです。
これだけじゃ使いづらいですね。さすがに。

なんか方法思いついたらまた書きます。