PR

1月27日 基本情報技術者『実戦問題』のアルゴリズムの章でこうしろうが,「うーん,わからん」となったのは選択ソートのフローチャート(流れ図)に関する問題だった。

問題.選択ソートを使って,配列Tに格納されたn個のデータを昇順に整列する次の流れ図の空欄aに入れるべき適切な条件はどれか。



 「フローチャート」懐かしい響きである。筆者,20代の前半まではCOBOL言語でホストコンピュータやオフコン(オフィス・コンピュータの略語であるが英語ではない。そもそもオフィス・コンピュータという概念が日本独自のものである。CPUは80X86系のものが多かったので,ハード的にはPCに近かったのだろう。その割に高価だったが…)のプログラムや,プログラム仕様書にプラスチック製のテンプレートでバッチ処理のフローばっかり書いていた。だから,フローチャートはいたって得意なのだ。エヘン!

 なんて,古臭い知識を自慢していないで,若い読者のためにバッチ処理についても説明しておこう。ブラウザを開いて,商品の注文サイトで商品を選び数量を入力,注文ボタンをクリックして完了。っていうのがオンライン処理。その後,注文を受けたコンピュータが一日の注文データをまとめて集計したり,売上伝票を印刷したりするのがバッチ処理。人間の操作による介入がないので,流れるようにフローチャートで処理を定義できるのである。いささかかカビ臭い感じもするが,知っておいた方が良い表現方法である。

 「こうしろう,それ,どんだけ頭の中で考えても,わからんちゃ」(うーん。今日もかなり富山弁)「紙に配列を書いてみて,ループ1ごとに配列の中の値がどう置き換わるか書いていけば,すぐわかるよ」

 選択ソートでは下図のように値を並べ替えていく。



 先に言っちゃうと,答えはエのT(p)>T(j + 1)である。
 
 ループ1は,例えばC言語で書くと for(i = 1; i < n - 1; i++ ) と,ループ2はfor(j = i; j < n - 1; j++) となる。順を追って説明していこう。まず,ループ1の始端でiが1になる。i → pでpも1になる。次にループ2の始端でj = i,つまりjも1になる。問題のaの箇所でT(p)>T(j + 1) = T(1)>T(1 + 1),つまり7が2より大きいかを判断している。Yesなので,j + 1(= 2)をpに入れる。

 ループ2はj < n - 1の間繰り返される。2回めのループ2ではT(2)より小さい値がないかT(3)以降と比較していく。あった場合は,その添え字をpに入れていく。比較は配列の終端まで繰り返される。この例では,T(2) = 2が一番小さい値なので,ループ2の終了時にT(p) = T(2)とT(i) = T(1)を入れ替える。結果T(1)には配列中で一番小さい値2が入り,T(2)にはT(1)に入っていた7が入る。ループ1の始端に戻りiに1を加算して,次に小さい値をT(2)に入れる処理が繰り返される。

 ループ1終了時点では,昇順に値が並んだ配列Tができあがるのである。