ビット単位でソートする。

ranking_tiemr / clock type : RealCPUClock / compile mode : RELEASE

1       / qsn   / 3713728.000000

2       / quicksort     / 17255964.000000

3       / quicksort_reverse     / 17416179.000000

4       / shellsort     / 39237981.000000

5       / shellsort_reverse     / 39519265.000000

6       / inssort_reverse       / 10238731538.000000

7       / inssort       / 12898124097.000000

続行するには何かキーを押してください . . .

uint32型の変数*1をソートしたいと思う。しかし、ある程度の順番でよい。という事で考えたのはビット単位で仕分けする方法。約4.64倍速い。
しかし最初から一つの配列に入れなければ良いじゃないかという話。なお、完璧にソートしたい場合はquicksortのみでソートした方が速い。つまりこのプログラムは使用用途の無い駄作である。

struct QSN{



typedef std::vector<int> ct;

	ct x[32];

	void reserve(size_t siz){
		for(int i=0;i<32;i++)
			x[i].reserve(siz);
	}
	void qsn(int n,int *a){

		int i,j;
		//ct x[32];
		for(i=0;i<n;i++){
			size_t ost = 32 - dkcNLZ((uint32)a[i]);
			x[ost].push_back(a[i]);
		}
/*		for(i=0;i<32;i++)
			quicksort<int>(x[i].size(),&(x[i][0]));

		for(i=0,j=0;i<32;i++){
			for(ct::iterator it = x[i].begin();it != x[i].end();it++){
				a[j] = (*it);
				j++;
				if(j < n){}else{break;}
			}
		}
*/
	}

};

*1:unsigned int (32bit環境)