ページ 11

フローチャート

Posted: 2007年7月26日(木) 10:12
by ロキ
↓のプログラムのフローチャートがかけません。教えてくれる方いましたらお願いします。


適当な数(ピボットという)を選択する (データの中央値が望ましい)
ピボットより小さい数を前方、大きい数を後方に移動させる (分割)
二分割された各々のデータを、それぞれソートする
実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。

ピボットとして一つ選びそれをPとする。
左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

Re:フローチャート

Posted: 2007年7月26日(木) 11:07
by 組木紙織
クイックソートのアルゴリズムですね。
ソースなら探せば色々なところで見つかりますが、フローチャートとなると。。。

というより再帰を使ったプログラムをフローチャートで書けるのかなというところが気になります。
少し考えてみたいとおもいます。

Re:フローチャート

Posted: 2007年7月26日(木) 12:40
by ロキ
早い返信ありがとうございます。

自分でも考えていますがどうもフローチャートは・・・Google検索でもフローチャートはクイックソートのフローチャートは中々ないようでのので;