アルゴリズム
| ■ アルゴリズムとは |
プログラムは、作成する人がどのように考えたかによって異なるプログラムが作成されます。プログラムの手順のことをアルゴリズムと言い、同じ処理をするプログラムの手順が異なる時、「アルゴリズムが違う」と言います。 プログラムを作るということは、つまりアルゴリズムを見つけることです。 この手順が見つかれば、あとはその手順をプログラミング言語を用いて記述すればよいのです。したがって、プログラム作成で最も困難なことは、アルゴリズムを見つけることです。それは「問題の解き方」を見つけることですから難しいわけです。
|
| ■ 分類の種類 |
数値や文字を順番に並べるという処理は、コンピュータの処理としてはしばしばあります。このようなプログラムのことをソートあるいは分類などと呼びます。 ソートの種類には、次のようなものがあります。
|
| ■ 分類のアルゴリズム |
上記のうち１。の主記憶装置にあるデータの並べ変えを中心に次の２つのアルゴリズムを説明しましょう。
|
| ■ 基本選択法 |
このアルゴリズムは、列べられたデータの中で最も小さい(あるいは大きい)データを選択して、それを列の最初のデータと交換します。そして、最初のデータは除いて、残りのデータに対して同じことを繰り返します。 この方法で５つのデータを小さい順に列べ変える手順を図で説明したものが以下です。
このプログラムは、配列のデータから最小値を見つけるアルゴリズムと似ています。 大きい順に並べ変える時は、最大値を見つけるアルゴリズムを参考にするとよいでしょう。 上記の説明で「交換する」というのがあります。これは２つの場所の中身を置き換えることに似ています。このような場合、ひとつ別の場所を用意しておいて、それを使って置き換えます。例えば、aとbの値を交換する場合、xという余分の領域を使って、次のようにしてaの中身とbの中身が入れ換えられます。
|
| ■ バブルソート |
このアルゴリズムは、配列に並んだデータの隣どうしを比較します。そして、もし並ぶ順が逆の場合は、その２つのデータを交換します。 配列の最初から終わりまで隣どうしを比較し、一度も交換することがなかったら、それはデータが並んでいるということです。そこで、このような状態になるまで、繰り返し配列の初めから終わりまで、隣どうしを比較する処理をし、一度も交換しなかったら終わりにします。上記と同じデータでバブルソートした場合の状態を図に書くと、次のようになります。
このなかで最も小さい数 "2"が、繰り返すたびに上に上がって行くのがわかるでしょう。これが水の中の泡が上に上がっていく状態に似ているので、このアルゴリズムはバブルソートと呼ばれています。 上記の例では３回繰り返したところですべて並びましたが、最初のデータの状態によっては、何回も繰り返す必要があります。つまり「1度も交換することがなかった！」ということになるまで繰り返し調べる必要があります。したがって最初のデータの状態により早く終わったり時間がかかったりします。 それに対して、基本選択法はデータの数により実行時間は決まります。例え最初の状態がすでに並んでいたとしても一定の時間がかかります。このように、アルゴリズムによって実行時間に特徴があります。 |
|
|