概ね方位不定だが多分割と偏っている
スポンサーサイト
--年--月--日 (--) | 編集 |
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


C アルゴリズム演習5
2006年09月03日 (日) | 編集 |
4すっとばして5。
4はハノイの塔というアルゴリズムだったのだが見てもさっぱり分からなかった故。

今回のアルゴリズムはソートについてだ。
ソートってのは並べ替えの事だな。エクスプローラとかでもお馴染みの筈だ。
が、サイズとか日付とかはよく分からんので今回は値の大小で判断してソートしてみる。

勝利条件:
「与えられたデータを小さい順に並べるプログラムを組む」



ソートもまた、ひとつの方法に限られず様々な手法で実現出来るそうだが、今回は基本選択法というアルゴリズムを用いるそうだ。
n個のデータがあった場合、まずその最小のモノを探し出し、1番目のモノと交換し、次に残ったn-1個のデータからまた最小のモノを探し出し、今度はそれを2番目のモノと交換する。そしてこれをn-1回(5個のデータなら4回)繰り返せばソート完了というわけだ。
これが基本選択法だな。

void main(void)
{
 static int a[]={3,5,9,7,8,2,6,4,1};
 int i,j,min,s,dumy;
 for(i=0;i<8;i++){
  min=a[i];
  s=i;
   for(j=i+1;j<9;j++){
    if(a[j]     min=a[j];
     s=j;
    }
   }
 dumy=a[i]; a[i]=a[s]; a[s]=dumy;
 }
  for(i=0;i<9;i++)
   printf("%2d",a[i])
}


こんな感じになる。
ぱっと見じゃよく分からないことも多いので順番に見ていくことにする。

最初のループで、

 for(i=0;i<8;i++){
  min=a[i];
  s=i;


n-1回、a[0]~[7]それぞれにおいて最小のモノとする、というプロセスを繰り返す。a[8]が無いのはa[7]までソートすれば自然に最後の1個が決まるからだな。多分。sは何項の値が最小か、を意味する変数なのだろう。

で、次のループの

   for(j=i+1;j<9;j++){
    if(a[j]     min=a[j];
     s=j;
    }
   }


で、最初に使われたa[i]を以降(a[0]ならa[1]以降)の値と比較して、より小さいものがあれば最小のモノとして値を代入するということを繰り返す。ここら辺は以前行った最大、最小を求めるアルゴリズムと同じだな。
ここでも最小の項を特定する為にsにjの値を代入する。
で、ループ閉じる。

そして、

  dumy=a[i]; a[i]=a[s]; a[s]=dumy;
 }


a[i]の値と最小の値を交換する。
が、一足飛びにa[i]とa[s]の値を交換することは出来ない(そういう関数もあるのかもしれないが現時点の俺は知らない)ので、先にa[i]かa[s]、どちらかの値を別の変数に格納しておいてから片方を移し、残った片方に別の変数から代入する、といった方法を用いる。
変数dumyは一時的にa[i]の値を格納する変数として、ここで使うわけだな。
これでa[i]と最小の値を持つ項a[s]を交換することが出来たので、後は最初のループに戻ってa[i]に+1し、a[7]になるまで同様に繰り返して終わり。

やってることは

a[0]を最小と仮定して、
a[1~8]と比較して、
より小さいモノがあればa[0]と値を交換する、
ということをa[7]まで繰り返す、

というだけなんだが妙にややこしい。
自分で言っててよく分からねー。実際に値を入れてみるか。

i=0の時、
最小の値minをa[0]=3とする。
min=3
s=i=0


a[j]=[i+1]=a[1]からa[8]まで、つまりj=1~8まで、
min(=3)より小さい値があればminにその値を代入し、その時のa[j]、jの値をsに代入する、ということを繰り返す。
この場合はa[8]の1が最終的にminに代入される値になる。
min=a[8]=1
s=8


dumyにa[i](=a[0])の値(=3)を代入し、a[i](=a[0])にa[s](=a[8])の値(=1)を代入し、a[s](=a[8])にa[i](=a[0])の値を代入する。

a[0]=1
a[8]=3
a[]={1,5,9,7,8,2,6,4,3};


これでa[i](=a[0])に最小の値が代入され、最小の値(=1)を持っていた項a[s](=a[8])にa[i](=a[0])の値が代入された。後はこれをa[7]まで繰り返せばソート完了。

まあ合ってるな。

sort_test.jpgsort_test2.jpg
この通り

ソートは頻繁に使われている機能だが、実際にやってみるとなると結構難儀やね。
スポンサーサイト

コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。