バケットソート

ソートしたい数列の最小値が1、最大値が100とする。このとき、数値を記憶する領域(バケット)を100個用意する。

数列の中に10という数値があるときは10番目のバケットに数値を放り込む。17という数値があるときは17番目のバケットに放り込む。すべての数値を放り込んだら、バケットから数値を取り出して整列させる。

数列の長さが20、最小値1、最大値10000というような場合、問題の大きさに対してバケットの数(作業領域)が大きくなりすぎる欠点がある。

その問題さえクリアできれば計算量はオー記法でO(n)であり、非常に高速にソートを行なうことができる。

その仕様上、整数値しかソートができない。