2009年01月30日21:46

基本情報技術者試験 H19春午前問14

金曜日「情報処理シリーズ」の２４回目です。

前回は平成１９年度春期午前問題・問13（文字列検索の流れ図）を解きました。

※金曜日は情報処理技術者をこれから目指したい方向けの記事となります。
ブログに使える時間の範囲内で詳しい解説を心がけますが、単語の意味や定義
をゼロから学びたい！という方には、きくちはじめ工房の情報処理試験・受験
対策レッスン（月謝制）をご提供していますのでご利用ください～。

今日は、平成１９年度春期午前問題・問14 を解いていきます。

問14：

配列 A[i] (i=1,2,・・・,n) を, 次のアルゴリズムによって整列する。
行2～3の処理が初めて終了したとき, 必ず実現されている配列の状態はどれか。

【アルゴリズム】

行
１　i を 1 から n-1 まで1ずつ増やしながら行2～3を繰り返す
２　　j を n から i+1 まで１ずつ減らしながら行3を繰り返す
３　　　もし A[j] < A[j-1] ならば, A[j] と A[j-1] を交換する

ア　A[1]が最小値になる
イ　A[1]が最大値になる
ウ　A[n]が最小値になる
エ　A[n]が最大値になる

解説：

配列を整列するアルゴリズムの中でも、最も基本的な

バブルソート(バブル(泡)がぶくぶくと移動するような

動きをすることから名付けられています)と呼ばれる

アルゴリズムの１種ですね。

問題文から、行1,2,3 が各１回終わった時の状態を

答える問題なので、

「どちらの方向(左(添え字小)または右(添え字大))にソートするか？」

を読み解ければ良い訳です。

慣れるまでの間は、具体的に書き出しながらやってみると

イメージしやすくなります。そうすれば、この整列は

「最小値を左(添え字小)へ左へと集める整列法」

だということが分かるので、答えは

ア　A[1]が最小値になる

が行3の初回完了時に必ず実現されている状態となります。

それではまた来週をお楽しみに～。