アカウント名:
パスワード:
↓真のプログラマが知ってる(ふりをする)べき{アルゴリズム,データ構造,定理,その他}
五種類以上のソートアルゴリズム
# 私はプログラマじゃないのでバブルソートしかしりません
コムソートあたりは覚えておくと非常に使い勝手がいいですよ。ソートしたい、でも言語の組み込みソートetc.は適用できない、だからってバブルソートとか書いて出したら殺される、でもクイックソートなんてめんどくさくて書きたくない…そんな時に役立つ、さくっと書ける上に結構早いというナイスなソートです。バブルソート+αだから覚えるのも苦じゃないですしね。
>トリッキーに見えるソートは書かないようにしています。
マージソートは再帰による分割統治が非常に美しくはまった分かりやすいソートだと思いますけど。ヒープソートって十分トリッキーじゃないですか？特に配列上にヒープを構成する方法とか。ヒープソートを使うような場所ならコムソートが代かえとして優れていると思います。まあ、シェルソートがトリッキーだと言われるくらいだからコムソートもトリッキーと言われそうですが。
#コムソートの難点は計算量の根拠が私には分からないこと...orz#平均・最悪ともにO(nlogn)らしいんですが、ほんまかいな。
#コムソートの難点は計算量の根拠が私には分からないこと...orz
すごい簡単なのに…。コムソートの比較回数はソート対象数をNとすると1主ループ目：N-N/1.3=(1.3-1)N/1.3=0.3N/1.3≒0.23N2主ループ目：N-(N/1.3)/1.3=N-N/1.32=(1.32-1)N/1.32=0.69N/1.32≒0.41Ni主ループ目：N-N/1.3i=(1.3i-1)N/1.3i となり、主ループはN/1.3n＝1で終了ですから、主ループ回数nはn=log1.3Nとなります。
＃厳密には整数除算するとか、主ループ内の比較回数はN-N/1.3i-1じゃね？とかあり
バブルソートとコムソートの間にはシェルソートがあるんだけど、無視される事が多いような。なんでだろ？
実際にプログラムしてみて、速度を比較すると分かるんですが、シェルソートの方が遅いんですよ。計算量の式がO(N^1.25)という変わり種なのも心理的障壁になっているのかも。やっぱ、O(N・log N)の方が素性が良さそうな気がする。
#でも入門書などではシェルソートの方がコムソートよりメジャーですよね？
>> #でも入門書などではシェルソートの方がコムソートよりメジャーですよね？
それは、入門書を書いてるやつらが、それ以前の入門書をコピーしてるから。コムソートは（自分の知る限り）２０年くらい前に発表されたはずだから、それ以上前から延々とコピーされ続けてるよね。
ＰＳ．コムソートって、シェルソートをチューニングしたものだから、もう少しシェルソートに敬意を払っても良いんじゃね
クイックソートが面倒くさいなんて，絶対に真のプログラマじゃないね．再帰が理解できてれば，ちょー簡単なのに．
問題は，クイックソートは最悪時の挙動が悪すぎるので，現実的に使うには最悪時に何らかの別のソート手法に切り替えるロジックを組み込まなければならないことだ．そういうことまで込みにして，クイックソートは面倒だというなら納得するけどな．
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー
真のプログラマが知ってる(ふりをする)べき〇〇 (スコア:1)
↓真のプログラマが知ってる(ふりをする)べき{アルゴリズム,データ構造,定理,その他}
Re: (スコア:0)
五種類以上のソートアルゴリズム
# 私はプログラマじゃないのでバブルソートしかしりません
Re:真のプログラマが知ってる(ふりをする)べき〇〇 (スコア:1)
コムソートあたりは覚えておくと非常に使い勝手がいいですよ。
ソートしたい、でも言語の組み込みソートetc.は適用できない、だからってバブルソートとか書いて出したら殺される、でもクイックソートなんてめんどくさくて書きたくない…そんな時に役立つ、さくっと書ける上に結構早いというナイスなソートです。
バブルソート+αだから覚えるのも苦じゃないですしね。
Re:真のプログラマが知ってる(ふりをする)べき〇〇 (スコア:1)
以前、シェルソートを書いて文句を言われたので、トリッキーに見えるソートは書かないようにしています。
notice : I ignore an anonymous contribution.
Re: (スコア:0)
>トリッキーに見えるソートは書かないようにしています。
マージソートは再帰による分割統治が非常に美しくはまった分かりやすいソートだと思いますけど。
ヒープソートって十分トリッキーじゃないですか？特に配列上にヒープを構成する方法とか。
ヒープソートを使うような場所ならコムソートが代かえとして優れていると思います。
まあ、シェルソートがトリッキーだと言われるくらいだからコムソートもトリッキーと言われそうですが。
#コムソートの難点は計算量の根拠が私には分からないこと...orz
#平均・最悪ともにO(nlogn)らしいんですが、ほんまかいな。
Re:真のプログラマが知ってる(ふりをする)べき〇〇 (スコア:1)
ここまで古典的なアルゴリズムだと、知らない人はいない事になっているらしいです。
# なんだか「不勉強な元プログラマの上司」対策の話になっているような……
notice : I ignore an anonymous contribution.
Re: (スコア:0)
#コムソートの難点は計算量の根拠が私には分からないこと...orz
すごい簡単なのに…。
コムソートの比較回数はソート対象数をNとすると
1主ループ目：N-N/1.3=(1.3-1)N/1.3=0.3N/1.3≒0.23N
2主ループ目：N-(N/1.3)/1.3=N-N/1.32=(1.32-1)N/1.32=0.69N/1.32≒0.41N
i主ループ目：N-N/1.3i=(1.3i-1)N/1.3i
となり、主ループはN/1.3n＝1で終了ですから、主ループ回数nはn=log1.3Nとなります。
＃厳密には整数除算するとか、主ループ内の比較回数はN-N/1.3i-1じゃね？とかあり
Re: (スコア:0)
Re: (スコア:0)
バブルソートとコムソートの間にはシェルソートがあるんだけど、無視される事が多いような。なんでだろ？
Re: (スコア:0)
実際にプログラムしてみて、速度を比較すると分かるんですが、
シェルソートの方が遅いんですよ。
計算量の式がO(N^1.25)という変わり種なのも心理的障壁になっているのかも。
やっぱ、O(N・log N)の方が素性が良さそうな気がする。
#でも入門書などではシェルソートの方がコムソートよりメジャーですよね？
Re: (スコア:0)
>> #でも入門書などではシェルソートの方がコムソートよりメジャーですよね？
それは、入門書を書いてるやつらが、それ以前の入門書をコピーしてるから。
コムソートは（自分の知る限り）２０年くらい前に発表されたはずだから、
それ以上前から延々とコピーされ続けてるよね。
ＰＳ．
コムソートって、シェルソートをチューニングしたものだから、もう少しシェルソートに敬意を払っても良いんじゃね
Re: (スコア:0)
クイックソートが面倒くさいなんて，絶対に真のプログラマじゃないね．再帰が理解できてれば，ちょー簡単なのに．
問題は，クイックソートは最悪時の挙動が悪すぎるので，現実的に使うには最悪時に何らかの別のソート手法に切り替えるロジックを組み込まなければならないことだ．そういうことまで込みにして，クイックソートは面倒だというなら納得するけどな．