「真の Geek が知っている (ふりをする) べき 9 つの式」記事へのコメント

真のプログラマが知ってる(ふりをする)べき〇〇

[Anonymous Coward]

↓真のプログラマが知ってる(ふりをする)べき{アルゴリズム,データ構造,定理,その他}

Re:

[Anonymous Coward]

五種類以上のソートアルゴリズム

# 私はプログラマじゃないのでバブルソートしかしりません

Re:

[Angelica (23122)]

コムソートあたりは覚えておくと非常に使い勝手がいいですよ。
ソートしたい、でも言語の組み込みソートetc.は適用できない、だからってバブルソートとか書いて出したら殺される、でもクイックソートなんてめんどくさくて書きたくない…そんな時に役立つ、さくっと書ける上に結構早いというナイスなソートです。
バブルソート+αだから覚えるのも苦じゃないですしね。

Re:

[Dobon (7495)]

手抜きなら単純選出法、そうでなければヒープソートかマージソートが無難では？

以前、シェルソートを書いて文句を言われたので、トリッキーに見えるソートは書かないようにしています。

--
notice : I ignore an anonymous contribution.

Re:

[Anonymous Coward]

>トリッキーに見えるソートは書かないようにしています。

マージソートは再帰による分割統治が非常に美しくはまった分かりやすいソートだと思いますけど。
ヒープソートって十分トリッキーじゃないですか？特に配列上にヒープを構成する方法とか。
ヒープソートを使うような場所ならコムソートが代かえとして優れていると思います。
まあ、シェルソートがトリッキーだと言われるくらいだからコムソートもトリッキーと言われそうですが。

#コムソートの難点は計算量の根拠が私には分からないこと...orz
#平均・最悪ともにO(nlogn)らしいんですが、ほんまかいな。

Re:真のプログラマが知ってる(ふりをする)べき〇〇

[Anonymous Coward]

#コムソートの難点は計算量の根拠が私には分からないこと...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.3²=(1.3²-1)N/1.3²=0.69N/1.3²≒0.41N
i主ループ目：N-N/1.3ⁱ=(1.3ⁱ-1)N/1.3ⁱ
となり、主ループはN/1.3ⁿ＝1で終了ですから、主ループ回数nはn=log_1.3Nとなります。

＃厳密には整数除算するとか、主ループ内の比較回数はN-N/1.3ⁱ-1じゃね？とかありますがご愛嬌ｗ

#平均・最悪ともにO(nlogn)らしいんですが、ほんまかいな。

最良でも比較回数は必ずO(NlogN)ですぜ～ｗ

ちなみに、計算間違いがあっても当方は一切感知しません。

Re:

[Anonymous Coward]

最後(間隔1)のループが何回で終わるか見積もらないといけないよhttp://science.srad.jp/users.pl