ITの基礎知識|ITパスポート・基本情報

基本情報技術者 平成19年春 問14

2017.10.04

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

[アルゴリズム]

  1.  iを1からn-1まで1ずつ増やしながら、行2~3を繰り返す。
  2.   jをnからi+1まで1ずつ減らしながら行3を繰り返す。
  3.    もしA[j]<A[j-1]ならば、A[j]とA[j-1]を交換する。
  • ア:  A[1]が最小値になる。
  • イ:  A[1]が最大値になる。
  • ウ:  A[n]が最小値になる。
  • エ:  A[n]が最大値になる。

 

Show answer

正解: ア

解説:

 

問題の処理内容は、バブルソート(基本交換法)になっている。

行1は「iを1からn-1まで1ずつ増やしながら、行2~3を繰り返す」であり、求められているのは「行2~3の処理が初めて終了した時」の状態であるので、行1の初回であるiが1である場合の処理結果となる。

つまり、行2は「jをnから2まで1ずつ減らしながら行3を繰り返す」となる。そのため、行3の繰り返しは、
A[n]<A[n-1]ならA[n]とA[n-1]を交換 から始まり、
A[2]<A[1]ならA[2]とA[1]を交換 までとなる。

要するに、最小値が前の要素になるように交換していくので、行2~3が初めて終了した時(i=1の場合の処理が終わったとき)には、A[1]には最小値が入っていることになる。