アカウント名:
パスワード:
バケットソートをよく使っています。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
私もバケツソートが多いです。ソートすべき値の要素数が多い場合は、大まかなカテゴリでバケツソートしてから、各バケツの中を再帰的にソートします。
物理的なモノの場合、一列に並べて自由にアクセスしたり交換したりできる数に限りがあり、積み上げておくと途中から取り出したり途中に挿入する操作が面倒、という性質があるので、「ランダムアクセスではなく、限られたスタックとキューだけが使える」という制約の上での適したアルゴリズムを考える必要がありますよね。クイックソートもキューだけでできますが、手数を考えるとバケツソートの方が楽なような。制約つきで最適なアルゴリズムの考察ってどこかにないかなあ。
人間の場合、各要素がある程度自律的に動けるのでなるべく並列にできるアルゴリズムが良いですが、これもぱっと考えるとバケツソート(必要なら多段で)がベストのように思えます。より良い方法はあるでしょうか。
私も普段は主にバケットソートでやってますが、バケットソートを再帰的にやるぐらいなら、タレコミにも挙げられてる基数ソート [wikipedia.org]を使うべきですね。
バケットソートを再帰的にやってると各桁毎にバケツを並べる必要があるので、作業面積がどんどん増えていきます。
基数ソートの場合、全データに対し桁毎バケットソートを繰り返すだけですので、作業領域が一定で済みます。
#最大の難点は、ちょっと直感的ではないってことですかね。先に下の位からソートを始めるので、作業途中は、一見「順番がバラバラ」で「部分的にソートされた小領域」が存在しません。「最後の最後でやっと完全にソートされた列がいきなり現れる」ので、一度基数ソートを始めたら他の方法に変えるのは無理で、基数ソートを最後までやりとげる必要があります。
あっと、書き忘れてた。基数ソートは「安定なソート」じゃないとダメというのが、物理ソートしてるときのネックです。
「1の位は昇順になっている(10の位の順番はてんでばらばら)」の列を、10の位だけを見て「安定なソート」をすれば、「10の位が等しいものは元の順番のまま=1の位の昇順に並ぶ=10の位とと1の位の二桁で昇順に並ぶ」というのが基数ソートのキモなわけですが、
人が手で仕分けするバケツソートは、単純に「元の山の上から1枚取って、該当する桁の山の上に置く」という操作になると、上下の並びが入れ替わるんですよね。基数ソートするためには、安定なソートにするために、「元の山の上から1枚取って、該当する桁の山の上に、ひっくり返して置く」必要があります。このひっくり返す手間が意外とバカにならないというか頭を真っ白にした単純作業の妨げになったりします。
#手順としては下から1枚取って山の上に置く、でもいいんだけど、下から取ると取り出すまで画像認識できないのでタイムラグが発生してさらに遅くなったりします。
抽象化して考えるとそうなんですが、現実だと山の大きさと扱いやすさにトレードオフがあるので、「そこそこの数に山が分割された状態」を保つ方がやりやすかったりします。
例えば数年分の月刊雑誌をソートするとき、年度でバケツソートすると、各バケツの山は物理挿入ソートが可能なくらいの大きさになるとか。
大量のカードのスタック、とかになればそれはまた別ですね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
クラックを法規制強化で止められると思ってる奴は頭がおかしい -- あるアレゲ人
バケットソートかなぁ (スコア:2, 参考になる)
バケットソートをよく使っています。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: (スコア:0)
私もバケツソートが多いです。ソートすべき値の要素数が多い場合は、大まかなカテゴリでバケツソートしてから、各バケツの中を再帰的にソートします。
物理的なモノの場合、一列に並べて自由にアクセスしたり交換したりできる数に限りがあり、積み上げておくと途中から取り出したり途中に挿入する操作が面倒、という性質があるので、「ランダムアクセスではなく、限られたスタックとキューだけが使える」という制約の上での適したアルゴリズムを考える必要がありますよね。クイックソートもキューだけでできますが、手数を考えるとバケツソートの方が楽なような。制約つきで最適なアルゴリズムの考察ってどこかにないかなあ。
人間の場合、各要素がある程度自律的に動けるのでなるべく並列にできるアルゴリズムが良いですが、これもぱっと考えるとバケツソート(必要なら多段で)がベストのように思えます。より良い方法はあるでしょうか。
Re:バケットソートかなぁ (スコア:1)
私も普段は主にバケットソートでやってますが、
バケットソートを再帰的にやるぐらいなら、タレコミにも挙げられてる基数ソート [wikipedia.org]を使うべきですね。
バケットソートを再帰的にやってると各桁毎にバケツを並べる必要があるので、作業面積がどんどん増えていきます。
基数ソートの場合、全データに対し桁毎バケットソートを繰り返すだけですので、作業領域が一定で済みます。
#最大の難点は、ちょっと直感的ではないってことですかね。
先に下の位からソートを始めるので、作業途中は、一見「順番がバラバラ」で「部分的にソートされた小領域」が存在しません。「最後の最後でやっと完全にソートされた列がいきなり現れる」ので、一度基数ソートを始めたら他の方法に変えるのは無理で、基数ソートを最後までやりとげる必要があります。
Re:バケットソートかなぁ (スコア:1)
あっと、書き忘れてた。
基数ソートは「安定なソート」じゃないとダメというのが、物理ソートしてるときのネックです。
「1の位は昇順になっている(10の位の順番はてんでばらばら)」の列を、10の位だけを見て「安定なソート」をすれば、「10の位が等しいものは元の順番のまま=1の位の昇順に並ぶ=10の位とと1の位の二桁で昇順に並ぶ」というのが基数ソートのキモなわけですが、
人が手で仕分けするバケツソートは、単純に「元の山の上から1枚取って、該当する桁の山の上に置く」という操作になると、上下の並びが入れ替わるんですよね。
基数ソートするためには、安定なソートにするために、「元の山の上から1枚取って、該当する桁の山の上に、ひっくり返して置く」必要があります。このひっくり返す手間が意外とバカにならないというか頭を真っ白にした単純作業の妨げになったりします。
#手順としては下から1枚取って山の上に置く、でもいいんだけど、下から取ると取り出すまで画像認識できないのでタイムラグが発生してさらに遅くなったりします。
Re: (スコア:0)
抽象化して考えるとそうなんですが、現実だと山の大きさと扱いやすさにトレードオフがあるので、「そこそこの数に山が分割された状態」を保つ方がやりやすかったりします。
例えば数年分の月刊雑誌をソートするとき、年度でバケツソートすると、各バケツの山は物理挿入ソートが可能なくらいの大きさになるとか。
大量のカードのスタック、とかになればそれはまた別ですね。