バケットソート - Wikipedia

バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。 バケットソートの概念 整列したいデータの取りうる値がm種類であるとき、m個のバケツを用意しておき、値ごとに1個のバケツを対応づける。元のデータ列を走査して、各データを対応するバケツに入れていく。この処理が終わった後、整列したい順序に従ってバケツから値を取り出せば、データをソートすることができる。 安定ソートを実現するためには、同じバケツに入っているデータは入れたときと同じ順序で取り出す必要がある。順

[okumuraa1]

ありがとうございますm(_ _)m

[otchy210]

そうか、スリープソートは空間軸の代わりに時間軸を使ったバケツソートだったのか。それは目から鱗だわ。次元を変換してるとか考えると、何か急にスリープソートが格好良く見えてきたぞｗ

[chezou]

"スリープソート バケットソートのバケツをメモリ空間の代わりに時間に置き換えたものである"

[sirocco]

話題の sleep sort はバケットソートらしい。あとでやってみよう。