最大値選択法

最大値選択なんですけれども
このフローチャートの意味がわかりません…ループの始まりと終わりの意味などはわかるのですが、交換や最大値x(k) → w 、x(i) → x(k)、w→ x(i）の部分が何を言いたいのか分らないんです。
宜しくお願いします。

　　　　（　　開　始　　）
　　　　　￣￣￣│￣￣￣
　　　　　───┴───
　　　　／　　交　換　　＼
　　　　│i =1,2,...,n-1│
　　　　└───┬───┘
　　　　┌───┴───┐
　　　　│　　i → k　　│
　　　　└───┬───┘
　　　　　───┴───
　　　　／　　最大値　　＼
　　　　│j=i+1,i+2,..,n│
　　　　└───┬───┘
　　　　　　　　│
　　　　　　　／　＼
　　　　　　／　　　＼　≦
　　(*) …／x(j)：x(k)＼───┐
　　　　　＼　　　　　／　　　│
　　　　　　＼　　　／　　　　│
　　　　　　　＼　／　　　　　│
　　　　　　　　│＞　　　　　│
　　　　┌───┴───┐　　│
　　　　│　　j → k　　│　　│
　　　　└───┬───┘　　│
　　　　　　　　│←─────┘
　　　　┌───┴───┐
　　　　│　　　　　　　│
　　　　＼　　最大値　　／
　　　　　───┬───
　　　　┌───┴───┐
　　　　│　x(k) → w 　│
　　　　│　x(i) → x(k)│
　　　　│　w　　→ x(i)│
　　　　└───┬───┘
　　　　┌───┴───┐
　　　　│　　　　　　　│
　　　　＼　　交　換　　／
　　　　　───┬───
　　　　　───┴───
　　　　（　　終　了　　）

No.3 ベストアンサー 回答者： kazumero 回答日時： 2007/07/27 00:53

No.2です。

i=1から順に追ってみましょう。
1 2 3
4 9 8
初めはk=1、j=2ですので、
k<4>とj<9>の比較です
jの方が大きいので、kはj、つまり2となります。
次は、k=2、j=3ですので、
k<9>とj<8>の比較です
kの方が大きいので何もしません。
そしてループを抜けて、交換します。
x(k)つまりx(2)と、x(i)つまりx(1)の交換です。
1 2 3
9 4 8
同様にしてi=2もやると
1 2 3
9 8 4
となります。

このプログラムですが、交換してる部分を見ると、最大値を選択するだけでなく、大きいもの順に並べ替えるプログラムであると言えます。

この回答へのお礼

フローチャートやループに対する知識もあいまいだったのでかなり悩んでたんですが、漸く分かりました＾＾；
丁寧に教えて頂き、本当にありがとうございました！

お礼日時：2007/07/27 23:17

No.2 回答者： kazumero 回答日時： 2007/07/26 23:10

最初の交換のところはループの条件が書いてあります。

iの値が1からn-1までループが続くってことですね。
んで最大値のところは、
jの値がi+1からnまでループが続くってことです。
何故このようなループ条件なのか。

全部で数がn個ありますよね。
数を比較する時、1番目の数と2番目の数、1番目の数と3番目の数・・・という風にしますよね。
これを表しています。

ループに初めてたどり着いた時を考えてみます。
iには1が入ってますよね？
とするとjはi+1ですので、2が入ってます。
iの値はkに代入されてるので、実際には、x(k)とx(j)、つまりx(1)とx(2)、つまりは1番目の数と2番目の数を比較しているわけです。

わかりにくかったらまた言ってください（＾＾；

この回答へのお礼

ありがとうございます。そこの部分もよく分かりました。
あとはなんというか表現しづらいのですが…i=1～n-1までループすると思うんですが、その際x(j)＞x(k)を満たすものはjがkになっていくんですよね？

例えば　4、9、8という列があるとすると
i=1からこの作業をやっていくと、i＝1の時x（1）をｘ（2）に代入、i＝2の時ｘ（2）はj→kの処理を受けないのでそのままになりますが、これは9がそのままになるのか、それとも9と交換した4がそのままになるのかどちらでしょう？あまり問題とは関係ないのですが気になってしまって…すみません＾＾；

お礼日時：2007/07/27 00:22

No.1 回答者： asuncion 回答日時： 2007/07/26 22:11

２つの値を交換するとき、ついつい

x(i) → x(k)
x(k) → x(i)
としそうになるかもしれません。

しかし、これは間違いです。
具体的な値を使ってやってみるとわかりますが、
２つの値は同じになってしまいます。

そうならないように、片方の値をいったん脇へどけておくための処理が
x(k) → w
です。こうしておくと、x(i)をx(k)に入れることができます。
この瞬間、x(i)とx(k)の値は同じですが、wにx(k)のもともとの値を
保存してありますので、２つの値はちゃんと残っています。
最後に、wに保存してあった値をx(i)に入れれば、
無事に交換が完成します。wはほったらかしにしておいてかまいません。

この回答へのお礼

詳しい回答ありがとうございます。
なるほど交換のところはよく分かりました。
ただ最初の交換のところと最大値のところの意味もよく分かりません。
なにぶんまだこういったことを勉強し始めたばかりなので…

お礼日時：2007/07/26 22:24