配列A[i] ( i = 1,2,・・・,n) を、次のアルゴリズムによって整列する。行2~3の処理が初めて終了した時、必ず実現されている配列の状態はどれか。
[アルゴリズム]
- iを1からn-1まで1ずつ増やしながら、行2~3を繰り返す。
- jをnからi+1まで1ずつ減らしながら行3を繰り返す。
- もしA[j]<A[j-1]ならば、A[j]とA[j-1]を交換する。
- ア: A[1]が最小値になる。
- イ: A[1]が最大値になる。
- ウ: A[n]が最小値になる。
- エ: A[n]が最大値になる。
配列A[i] ( i = 1,2,・・・,n) を、次のアルゴリズムによって整列する。行2~3の処理が初めて終了した時、必ず実現されている配列の状態はどれか。
[アルゴリズム]
正解: ア
解説:
問題の処理内容は、バブルソート(基本交換法)になっている。
行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]には最小値が入っていることになる。