［Ｑ］正４０角形の頂点に（辺と対角線のうち）８０本が引かれている．そのようなグラフのどこに三角形があるかを見つけだすアルゴリズムは？

　正４０角形には４０・３９／２＝７８０本の辺と対角線があり，そのうち８０本だけが線を引かれているという状況である．

　一般にｎ角形では（ｎ，３）組調べることが必要になるから，ｎが大きいとき（ｎ，３）＝ｎ^3／６，したがってＯ（ｎ^3）になるが，隣接行列の計算に代数的な工夫を加えたＯ（ｎ^2）アルゴリズムが知られている．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】ソート・アルゴリズム概説

　ランダムな順番で並んでいるデータを大きさの順に並べ換えて整列させることをソーティングといいます。ソーティングはデータ処理において基本中の基本となるもので、プログラムを作るにはプログラミング言語や計算機自体の知識のほかにこうした定石（アルゴリズム）についての理解が必要です。

　ソーティングには多くの方法があり、アルゴリズムによって大きくスピードが異なってきます。また、もともと同じ大きさのデータがもとの順序関係を崩さないような並べ換えを「安定なソート」とか「自然な振る舞いのソート」といいます。速いソート法は一般的に不安定で順序関係を保存することはできません。遅いソート法は大量のデータのソートには適しませんが、安定かつ原理が単純で理解しやすいため好まれています。

　ソートアルゴリズムにはそれぞれ利害得失があり、スピードだけで一概にその性能を評価することはできませんが、これらのアルゴリズムをインプリメン

トするときの便宜のために、下表のごとく３つのグループに分類しその性能を

整理しておきます。

アルゴリズム：実行時間

単純選択法：Ｏ（Ｎ^2）

改良選択法（ヒープ・ソート）：Ｏ（Ｎlog2Ｎ）

単純挿入法：Ｏ（Ｎ^2）　

改良挿入法（シェル・ソート）：Ｏ（Ｎ^1.2）

単純交換法（バブル・ソート）：Ｏ（Ｎ^2）

改良交換法（クイック・ソート）：Ｏ（Ｎlog2Ｎ）

　Ｏ（Ｎ^2）とはＮ^2に比例する実行時間が必要の意（Ｎ：データ数）。すなわち、Ｏ（Ｎ^2）ではデータ数が１００倍になると実行時間は１００００倍になります。したがって、単純選択法、単純挿入法、単純交換法はデータ数が多くなると極端に遅くなり実用的ではなくなります。

　メモリ中だけでソートすることを内部ソート（オンメモリ・ソート）といいますが、その中でもっとも平均的な効率のいい方法がクイック・ソートです。最高速だといわれているクイック・ソートでも、最悪の場合（元のデータが逆順に整列していた場合）にはＮ^2のオーダーの計算量となることがありますが、ごくまれなケースでありそのようなことはまずないと考えてよいでしょう。　なお、メモリに入り切らないような巨大なデータをソートするには外部ソートのテクニックが必要になってきます。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝