ソートアルゴリズム

少し前に先生がなうでボヤいていたので。

先生のなう

ソートアルゴリズムって懐かしい。

駆け出しのプログラマだった頃の練習問題。研修問題。

アルゴリズムごとのコストを数学的に計算（期待値の計算）することと、実際のデータを元に分布図を作成すること。


計算結果と実際のプログラムのprof結果が一致するかどうかの検証。

実は計算どおりにはいかない。プログラムの分岐によってCPUがフェッチしたキャッシュがクリアされてしまうので、理論値と実測地は微妙にずれる。このずれを補正するため（最速にするため）にコーディングを工夫したり、コンパイラのオプティマイズアルゴリズムを考える。


大学でコンピュータサイエンスを学んだ人にとっては、朝飯前だろう。

上記の問題をクリアできなければ、ただのアプリケーションプログラマとして配属される。まずは新入社員時の第一のふるいですね。