D言語遊び(Sortする)

昨日は無気力に11時間ぐらいやっていたので，今日は反省して勉強．

バケットソート(Bucket sort): O(n)．その分メモリが辛いです．

import std.stdio;
import std.array;

void main(){
	const int MAX_N = 9;
	int[] arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], res = [];
	int bucket[MAX_N+1];

	while(!arr.empty()){
		bucket[arr.front]++;
		arr.popFront();
	}
	for(int i=1;i<=MAX_N;i++){
		int t = bucket[i];
		for(;t;t--)
			res ~= i;
	}
	writeln(res);//=>[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
}

基数ソート(Radix sort): O(kN)(k:データの最大桁数)．バケットよりもメモリは楽になります．

import std.stdio;
import std.array;
import std.math;
import std.algorithm;
import std.conv;

void main(){
	int[] arr = [314, 141, 415, 159, 592, 926, 265, 653, 535, 358, 589], res = [];
	int[][] bucket;
	int MAX_R;
	bucket.length = 10;

	while(!arr.empty()){
		MAX_R = max(MAX_R, to!string(arr.front).length);
		bucket[arr.front%10] ~= arr.front;
		arr.popFront();
	}

	for(int i=1;i<MAX_R;i++){
		for(int j=0;j<=9;j++){
			int prevbn = bucket[j].length;
			for(int k=0;k<prevbn;k++){
				int g = bucket[j].front / pow(10, i) % 10;
				if(j != g){
					bucket[g] ~= bucket[j].front;
				}else{
					bucket[j] ~= bucket[j].front;
				}
				bucket[j].popFront();
			}
		}
	}
	
	for(int i=0;i<=9;i++){
		for(int j=0;j<bucket[i].length;j++)
			res ~= bucket[i][j];
	}
	
	writeln(res);//=>[141, 159, 265, 314, 358, 415, 535, 589, 592, 653, 926]
}

この2つのソートは取る値の範囲が分かっていて，メモリが十分間にあうときに使います．
実装が簡単，早いので好きになりました．