|
| 数学とＣＡＤ アルゴリズム、並べ替え（整列；ソート） |
ある問題があって、それを解くための概念や手法、手順のことを、アルゴリズムといいます。CADに限らず、プログラミングを行う際、「こういう事がしたい」→「そのためにはどうすればいいか？」→「どういう考え方をするか？ どういう手法を使えばいいか？」「どんな計算式を使えばいいか？」「どう組み合わせればいいか？」→「どういう風にプログラミングすれば良いか？」→プログラミング→テスト→デバッグ等→繰り返し？ ・・・ →目的のものが出来上がり！という具合になります。アルゴリズムの構築は、とても大切ですが、これを考える楽しみと、目的物が得られた時の喜び、そして、利用者に便利に使って貰えた時の喜びが、創造（クリエイティブ）の面白さかと思われます。プログラミングの最中には難儀するかもしれませんが、解決出来た時にはそんな事は吹き飛んでいる事でしょう。
まず、ある数値の集まりがあったとします。試験の成績かもしれませんし、気温や湿度などのデータかもしれません。
まずは、この中の最大値・最小値が知りたいとします。「見たら分かるじゃん、最大値は85で、最小値は5だろ」という感じですが、これをプログラムにします。例えば、言語処理系（例えば DelphiやVisual BASIC等）に、最初から、Max(〜)やMin(〜)といった関数があってそれを使えば終わり、という場合もあるでしょう。勿論それも解決法の１つですが、それを使わず、自分で手法を考える、というのも大切です。既にあるものを使うだけでお終い、なのであれば、作る楽しみというものも半減してしまいます。また、より難しい問題に直面した場合、考える訓練をしていないと解決出来ないかもしれません。
それでは、最大値を得る方法を考えて行きましょう。
まず最初の２つを比較します。「10」と「30」どちらが大きいか？「30」が大きいので「30」を覚えます。次に「15」と比較します。「30」の方が大きいです。次に「40」と比較します。「40」が大きいので「40」を覚えます。次に「20」と比較します。・・・と、順番に見て、比較して、全部見終わった時に、覚えているのが何か？それが最大値となります。
↓
↓
↓
↓
↓
↓
↓
↓
var
A : array[1..10] of Integer;
i,max : Integer ;
・・・
begin
・・・
max := 0;
for i:=1 to 10 do
if (max < A[i]) then
max := A[i];
・・・
end; |
var
A : array[1..10] of Integer;
i,max : Integer ;
・・・
begin
max := A[1];
for i:=2 to 10 do
if (max < A[i]) then
max := A[i];
end; |
最小値は、最大値とは逆に、小さい方を記憶していきます。平均値は、全ての値を加算して、数値の個数で割算すれば得られます。
さぁ次に、この数値の集まりを、小さいものから大きいものへ、順番に並べたいとします。例えば、試験の成績であれば、１位〜10位のランキング結果やワースト記録、等、実際、よく行われています。これを、並べ替え、整列、ソート、等と呼びます。並べ替えは、各数値を比較して小さいものと大きいものを入れ替える作業をしていきます。
★２値の交換
取りあえず、値を比較していって、入れ替え作業をしていけばいいじゃないか？ と、その前に、２つの値を入れ替えるというのはどういう処理なのでしょうか？
を入れ替えたい場合、50を70の場所に入れてしまうと
70という値が消えてしまいます。 ですので一旦、片方の値を逃がしてやる必要があります。
↓ そして逃がした方の値を、もう片方へ入れます。
これで２つの値の入れ替えが出来ました。
procedure swap(X,Y:Integer);
var
a : Integer ;
begin
a := X ;
X := Y ;
Y := a ;
end; |
取りあえず、値を比較していって、入れ替え作業をしていけばいいじゃないか？という事で、全ての値を順番に比較・交換作業をしていこう、というのが、バブルソートです。昇順（小→大）では、前の値が大きい場合に、値の交換を行います。
これで、１番目の値が一番小さい値になります。次に、２番目の値から同じように比較・交換を繰り返します。
次に、３番目の値から同じように比較・交換を繰り返します。
以降、９番目まで続けます。10番目は最後なのでありません。
プログラムは下記のようになります。
var
A : array[1..10] of Integer;
i,j : Integer ;
・・・
begin
・・・
for i:=1 to 9 do
for j:=i+1 to 10 do
if (A[i] > A[j]) then
swap(A[i],A[j]);
・・・
end; |
★選択法
まず、遅くなる原因の１つは、実際のデータの出し入れ、に時間が掛かっている現実を、なるべく回避しようという事で、選択法と呼ばれる手法があります。これは、内部ループで全ての値を入れ替えている処理を、１回だけの入れ替えにして、速度を速くしようとする手法です。つまり、内部ループで最小値を算出した結果を、最初の値と入れ替える処理を行います。
↓１番目の値と最小値[5]と入替 ↓２番目の値と以降の最小値[10]と入替 ↓３番目の値はそのまま ↓４番目の値と以降の最小値[20]と入替 ↓５番目の値と以降の最小値[30]と入替 ↓６番目の値と以降の最小値[35]と入替 ↓７番目の値と以降の最小値[40]と入替 ↓８番目の値と以降の最小値[60]と入替 ↓９番目の値と以降の最小値[70]と入替 ↓
完了
var
A : array[1..10] of Integer;
i,j,k : Integer ;
・・・
begin
・・・
for i:=1 to 9 do begin
k := i;
for j:=i+1 to 10 do
if (A[k] > A[j]) then
k := j; // kには最小値の位置が入る
swap(A[i],A[k]);
end;
・・・
end; |
数値の集まりを、親と２つの子の連続した木構造と想定し、親の値は子の値よりも大きい、という条件の成立させるように比較・入れ替え作業を行って行きます。木構造の一番上が最大値になります。１回の計算で最大値を算出し、一番最後のデータと交換します。１つ少なくなった数値の列から再度、最大値を算出し、という事を繰り返して行きます。
★クイックソート
基準値を想定して、基準値よりも小さい値を数値列の左側に、基準値よりも大きい値を数値列の右側に、集めます。左側の部分だけで更に基準値を設定して左右に分け、右側の部分だけで更に基準値を設定して左右に分け、という具合に分割していって、並べ替えを完了させる、という手法です。問題は基準値をどう取るか？ですが、この値によって、並べ替えの速度が変わってしまいます。通常は平均値が良いとされているようです。
その他、いろいろな並べ替えのアルゴリズムが研究されているようです。
| 簡単な並べ替えのサンプルプログラムです。10,000個の整数乱数値を発生させて動的配列に格納し、バブルソート、選択法、を行い、その掛かった時間を計測します。ついでに、TListBoxコンポーネント等には「Sorted」プロパティをTrueにする事で自動的にアルファベット順に並べ替えを行う機能がありますのでこれも一応見れるようにしておきます。 |
|
|
CAD装置(1)
CAD装置(2)
メディア
AutoCADの
DIESELマクロ
ＣＳＶ
ＤＸＦ
ＰＣＥＳ
ＩＧＥＳ
ＳＴＥＰ
数学とCAD
▲PREV
▼NEXT
CAD作ろ！
|
