今日の授業の概要

素朴なソーティングアルゴリズム（バルブソート、挿入ソート、選択ソート）

ここの主題は「計算効率の捉え方と見積り方法」です。

三種類の異なるソーティングアルゴズムはいずれも与えられた整数列を正順化して同じ出力を与えます。でも、もちろん動作は異なりますし、微妙な違いもあります。その違いをデータの比較回数やデータの代入回数などで比較することで、計算効率について学びます。アルゴリズムは計算を特定のプログラミング言語と独立して記述したものです。これは計算を特定のプログラミング言語と切り離して、計算の本質的な性質を議論するために必要なことです。また、計算効率の評価にあたって、特定のコンピュータやそのハードウェア構成に依存させないことも大切です。このために、プログラミング言語からも、コンピュータのハードウェア構成からも独立した評価尺度を用いて計算にかかる費用を見積りました。
再帰的で圧倒的に効率的なソーティングアルゴリズム（マージソート、クイックソート）

再帰的な技法を用いた二つのソーティングアルゴリズムを用いる、ここでの主題は素朴なソーティングアルゴリズムに比べて圧倒的に効率的なアルゴリズムの存在と、その計算効率の見積り方を学ぶことです。アルゴリズムの世界における、圧倒的な効率が物理的な世界での数％～数倍～桁違いの差などに比べて、次元を越えた性能差であることを学びました。

マージソートとクイックソートは問題を再帰的に二分していく点でよく似ています。前者は分割後にソート結果の統合のときにデータを融合するときに工夫が施され、後者は分割するときに順序を導入しています。
レポート2の予告

準備中です。レポートの詳しい内容を一両日中に発表します。