C言語: 2007年3月アーカイブ
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソート、バブルソートと来まして、今回はバケットソート(ビンソート)です。
原理は非常に単純です。
たとえば、1以上100以下の間のランダムな十個の数値をソートしたいとします。
あらかじめ、要素数100の配列を用意しておくのです。すべて初期値は0とします。
そして、十個の数値を一つずつ見て、配列のその数値と同じ添え字の要素の値を1増やします。
十個の数値を見終えたときに、格納値が0ではない要素の添え字だけを見ます。
そして1から(もしくは100から)順番に、格納値の数が0ではない要素の添え字を表示します。
格納値の数が1なら1回、2なら2回、格納値の回数表示します。
これでソートの完了です。
高速ではありますが、ソートする値の上限に合わせて要素を用意するため、非常にメモリ効率が悪い場合があります。
たとえば、並べ替えたい数は5個なのに、その値の範囲が1～30000だったなら、配列は30000個の要素を用意しないといけないのに、実際には多くともそのうちの5個しか使わないわけです。
また、値の範囲がわかっていない場合も使えません。
データが「５４５３１」のときの使用例は以下の通りです。
・配列をすべて0で初期化する。「配列[1]=0 配列[2]=0 配列[3]=0 配列[4]=0 配列[5]=0」
・一番左の数値と同じ配列の値を1増やす。「配列[5]=1」
・左から二番目の数値と同じ配列の値を1増やす。「配列[4]=1」
・左から三番目の数値と同じ配列の値を1増やす。「配列[5]=2」
・左から四番目の数値と同じ配列の値を1増やす。「配列[3]=1」
・左から五番目の数値と同じ配列の値を1増やす。「配列[1]=1」
・結果「配列[1]=1 配列[2]=0 配列[3]=1 配列[4]=1 配列[5]=2」
・格納されている値の数だけ添え字を表示する。「１３４５５」
以下、C言語で書いたバケットソートのプログラムです。
ソートを行う関数部分のみです。
/* バケットソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int max = 101 ;/* max：値の最大値+1 値は0～100と仮定*/
int array[max],i,j,k = 0 ; /* array：バケット */
for(i = 0 ; i < max ; i++)array[i]=0;
for(i = 0 ;i < num ; i++){
array[data[i]]++ ;
}
for(i=0 ; i < max ; i++){
for(j = array[i] ; j > 0 ; j--){
data[k++] = i ;
}
}
}
/* バケットソート関数ここまで */