ソートのアルゴリズムの中で最も単純などと言われるバケツソート。今回はバケツソートに関してまとめてみます。
バケツソートは他にバケットソート、分布数えソート、計数ソート、ビンソートなどとも呼ばれます。
バケットソートのアルゴリズム
今回の例では話を単純にするため、ソートしたい配列は1〜9までの数字が5つ順番がバラバラで収まっている配列とします。
バケットソートでは予めソートしたい配列の取りうる最大値を、元に番号を振ったバケットを用意します。これをバケット配列とします。
この例ではソートしたい配列は下記です。
ソート配列の値は9が取りうる最大値になるので、1〜9までの番号が振られたバケツを数字の順番通りに用意します。
バケット配列はこんな感じです。
これが用意できたらソート配列の値と、バケット配列の番号とを比較していきます。
ソート番号の値がバケツ配列の番号より大きい場合は次に進みまた比べます。
それを繰り返す内にソート配列の値がバケット配列の番号と等しくなる時があります。
その時、ソート配列の値を、番号が等しくなったバケツ配列に代入します。
これをソート配列のすべての値で行えば、ソート配列の値はすべてバケット配列の番号が等しい場所に代入されているはずです。
バケツ配列の番号はすでに揃っているので、あとはその順番を崩さぬよう、バケット配列の値の入っているところだけを順に左から引き出せば、昇順でソートされた結果を得ることができます。
バケットソートの利点と欠点
バケットソートの場合、ソートする入れるのとりうる最大値が配列数になってしまうので、もし1〜100万の数字を持っている配列をソートする際は、100万の長さに配列が必要になります。
このようにバケットソートはソートする入れるのとりうる最大値が大きいとリソースが増大する可能性があります。
そのためバケットソートは比較的短い配列をソートするのに向いているとされます。
またバケットソートは最大値（とりうる値の種類の数ともいえる）が重要になります。そのため最大値を知ることができない、配列の長さが分からない場合にはバケツを用意できないので、ソートのしようがなくなります。
データの状態に左右されてしまうのが欠点ではありますが、条件が整った場合にはかなり速くソートを行えるアルゴリズムです。
