「スラッシュドットに聞け：物理的にモノや人をソートするときはどうしてる？」記事へのコメント

バケットソートかなぁ

[Anonymous Coward]

バケットソートをよく使っています。http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88

Re:

[Anonymous Coward]

私もバケツソートが多いです。ソートすべき値の要素数が多い場合は、大まかなカテゴリでバケツソートしてから、各バケツの中を再帰的にソートします。

物理的なモノの場合、一列に並べて自由にアクセスしたり交換したりできる数に限りがあり、積み上げておくと途中から取り出したり途中に挿入する操作が面倒、という性質があるので、「ランダムアクセスではなく、限られたスタックとキューだけが使える」という制約の上での適したアルゴリズムを考える必要がありますよね。クイックソートもキューだけでできますが、手数を考えるとバケツソートの方が楽なような。制約つきで最適なアルゴリズムの考察ってどこかにないかなあ。

人間の場合、各要素がある程度自律的に動けるのでなるべく並列にできるアルゴリズムが良いですが、これもぱっと考えるとバケツソート(必要なら多段で)がベストのように思えます。より良い方法はあるでしょうか。

Re:

[taka2 (14791)]

私も普段は主にバケットソートでやってますが、
バケットソートを再帰的にやるぐらいなら、タレコミにも挙げられてる基数ソート [wikipedia.org]を使うべきですね。

バケットソートを再帰的にやってると各桁毎にバケツを並べる必要があるので、作業面積がどんどん増えていきます。

基数ソートの場合、全データに対し桁毎バケットソートを繰り返すだけですので、作業領域が一定で済みます。

#最大の難点は、ちょっと直感的ではないってことですかね。
先に下の位からソートを始めるので、作業途中は、一見「順番がバラバラ」で「部分的にソートされた小領域」が存在しません。「最後の最後でやっと完全にソートされた列がいきなり現れる」ので、一度基数ソートを始めたら他の方法に変えるのは無理で、基数ソートを最後までやりとげる必要があります。

Re:バケットソートかなぁ

[Anonymous Coward]

抽象化して考えるとそうなんですが、現実だと山の大きさと扱いやすさにトレードオフがあるので、「そこそこの数に山が分割された状態」を保つ方がやりやすかったりします。

例えば数年分の月刊雑誌をソートするとき、年度でバケツソートすると、各バケツの山は物理挿入ソートが可能なくらいの大きさになるとか。

大量のカードのスタック、とかになればそれはまた別ですね。