AFsoft WebSite(エーエフソフト・ウェブサイト)
 

オペレーティング・システムについて

プログラミングについて
ホームページについて
キャドについて
電子カタログについて
書籍・雑誌
イベント
リンク集
数学とCAD アルゴリズム、並べ替え(整列;ソート)
ある問題があって、それを解くための概念や手法、手順のことを、アルゴリズムといいます。CADに限らず、プログラミングを行う際、「こういう事がしたい」→「そのためにはどうすればいいか?」→「どういう考え方をするか? どういう手法を使えばいいか?」「どんな計算式を使えばいいか?」「どう組み合わせればいいか?」→「どういう風にプログラミングすれば良いか?」→プログラミング→テスト→デバッグ等→繰り返し? ・・・ →目的のものが出来上がり!という具合になります。アルゴリズムの構築は、とても大切ですが、これを考える楽しみと、目的物が得られた時の喜び、そして、利用者に便利に使って貰えた時の喜びが、創造(クリエイティブ)の面白さかと思われます。プログラミングの最中には難儀するかもしれませんが、解決出来た時にはそんな事は吹き飛んでいる事でしょう。
 
まず、ある数値の集まりがあったとします。試験の成績かもしれませんし、気温や湿度などのデータかもしれません。
1030154020570358560

まずは、この中の最大値・最小値が知りたいとします。「見たら分かるじゃん、最大値は85で、最小値は5だろ」という感じですが、これをプログラムにします。例えば、言語処理系(例えば DelphiやVisual BASIC等)に、最初から、Max(〜)やMin(〜)といった関数があってそれを使えば終わり、という場合もあるでしょう。勿論それも解決法の1つですが、それを使わず、自分で手法を考える、というのも大切です。既にあるものを使うだけでお終い、なのであれば、作る楽しみというものも半減してしまいます。また、より難しい問題に直面した場合、考える訓練をしていないと解決出来ないかもしれません。
それでは、最大値を得る方法を考えて行きましょう。
まず最初の2つを比較します。「10」と「30」どちらが大きいか?「30」が大きいので「30」を覚えます。次に「15」と比較します。「30」の方が大きいです。次に「40」と比較します。「40」が大きいので「40」を覚えます。次に「20」と比較します。・・・と、順番に見て、比較して、全部見終わった時に、覚えているのが何か?それが最大値となります。
1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

1030154020570358560

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;

のように考えたとします。一見これで正しいように見えます。しかし、データ A[]の中身が全てマイナス値だとしたら、この場合、初期値で与えた「0」が最大値になってしまいます。勿論、数値が正の値である、と確定していればこれでもOKです。しかし、負の値でも対応したいのであれば、maxの初期値を絶対に有り得ない小さい値にする、というのも1つの手法ですが、
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;

のようにして、一番最初の最大値は、1つ目のデータであるとしておき、ループは、2つ目のデータから比較開始します。
最小値は、最大値とは逆に、小さい方を記憶していきます。平均値は、全ての値を加算して、数値の個数で割算すれば得られます。
 
 
さぁ次に、この数値の集まりを、小さいものから大きいものへ、順番に並べたいとします。例えば、試験の成績であれば、1位〜10位のランキング結果やワースト記録、等、実際、よく行われています。これを、並べ替え、整列、ソート、等と呼びます。並べ替えは、各数値を比較して小さいものと大きいものを入れ替える作業をしていきます。
 
★2値の交換
取りあえず、値を比較していって、入れ替え作業をしていけばいいじゃないか? と、その前に、2つの値を入れ替えるというのはどういう処理なのでしょうか?
7050
を入れ替えたい場合、50を70の場所に入れてしまうと
70という値が消えてしまいます。
5050
ですので一旦、片方の値を逃がしてやる必要があります。
7050
70
5050
70
そして逃がした方の値を、もう片方へ入れます。
5070
これで2つの値の入れ替えが出来ました。
procedure swap(X,Y:Integer);
var
 a : Integer ;
begin
 a := X ;
 X := Y ;
 Y := a ;
end;
 
★バブルソート(基本交換法)
取りあえず、値を比較していって、入れ替え作業をしていけばいいじゃないか?という事で、全ての値を順番に比較・交換作業をしていこう、というのが、バブルソートです。昇順(小→大)では、前の値が大きい場合に、値の交換を行います。
1030154020570358560
1030154020570358560
1030154020570358560
1030154020570358560
1030154020570358560
↓交換
5301540201070358560
5301540201070358560
5301540201070358560
5301540201070358560
5301540201070358560

これで、1番目の値が一番小さい値になります。次に、2番目の値から同じように比較・交換を繰り返します。
5301540201070358560
↓交換
5153040201070358560
5153040201070358560



5103040201570358560

次に、3番目の値から同じように比較・交換を繰り返します。
5103040201570358560
5101540203070358560

以降、9番目まで続けます。10番目は最後なのでありません。
5101520403070358560
5101520304070358560
5101520303570408560
5101520303540708560
5101520303540608570
5101520303540607085

プログラムは下記のようになります。
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;

バブルソートで取りあえずは並べ替えを行う事は出来ます。しかし、値の数が多ければ多い程、どんどん、遅くなってしまいます。100個や200個でしたら、コンピュータの速度にも依りますが、さほどの時間は掛かりません。しかし何万・何十万となっていくと、かなりの時間を要してしまいます。そこで、高速に行うには、どうすれば良いか?どのようなアルゴリズムが良いのか?が古くから研究されています。
 
★選択法
まず、遅くなる原因の1つは、実際のデータの出し入れ、に時間が掛かっている現実を、なるべく回避しようという事で、選択法と呼ばれる手法があります。これは、内部ループで全ての値を入れ替えている処理を、1回だけの入れ替えにして、速度を速くしようとする手法です。つまり、内部ループで最小値を算出した結果を、最初の値と入れ替える処理を行います。
1030154020570358560
↓1番目の値と最小値[5]と入替
5301540201070358560
↓2番目の値と以降の最小値[10]と入替
5101540203070358560
↓3番目の値はそのまま
5101540203070358560
↓4番目の値と以降の最小値[20]と入替
5101520403070358560
↓5番目の値と以降の最小値[30]と入替
5101520304070358560
↓6番目の値と以降の最小値[35]と入替
5101520303570408560
↓7番目の値と以降の最小値[40]と入替
5101520303540708560
↓8番目の値と以降の最小値[60]と入替
5101520303540608570
↓9番目の値と以降の最小値[70]と入替
5101520303540607085

完了
プログラムは下記のようになります。
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;
 
★ヒープソート(二分木法)
数値の集まりを、親と2つの子の連続した木構造と想定し、親の値は子の値よりも大きい、という条件の成立させるように比較・入れ替え作業を行って行きます。木構造の一番上が最大値になります。1回の計算で最大値を算出し、一番最後のデータと交換します。1つ少なくなった数値の列から再度、最大値を算出し、という事を繰り返して行きます。
 
★クイックソート
基準値を想定して、基準値よりも小さい値を数値列の左側に、基準値よりも大きい値を数値列の右側に、集めます。左側の部分だけで更に基準値を設定して左右に分け、右側の部分だけで更に基準値を設定して左右に分け、という具合に分割していって、並べ替えを完了させる、という手法です。問題は基準値をどう取るか?ですが、この値によって、並べ替えの速度が変わってしまいます。通常は平均値が良いとされているようです。
 
その他、いろいろな並べ替えのアルゴリズムが研究されているようです。
 
TEST016
 <ソースDownLoad>
簡単な並べ替えのサンプルプログラムです。10,000個の整数乱数値を発生させて動的配列に格納し、バブルソート、選択法、を行い、その掛かった時間を計測します。ついでに、TListBoxコンポーネント等には「Sorted」プロパティをTrueにする事で自動的にアルファベット順に並べ替えを行う機能がありますのでこれも一応見れるようにしておきます。
 
 
▲PREV  ▼NEXT
CAD装置(1)
CAD装置(2)
メディア
AutoCADの
DIESELマクロ
CSV
DXF
PCES
IGES
STEP
数学とCAD
 ▲PREV
 ▼NEXT
CAD作ろ!
 
お問い合わせ 
本サイトはリンクフリーです
リンクバナー
(C)Copyright 1999-2015 By AFsoft All Rights Reserved.