BohYoh.com《基本情報技術者試験》2007年度＝平成19年度・春期午前問14

基本情報技術者試験

2007年度＝平成19年度・春期

午前

問14

　配列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]が最大値になる。

解答

ア

解説

　本問で問われているアルゴリズムはバブルソートです。このアルゴリズムでは、隣り合うデータを比較し、必要であれば交換を行うという一連の操作（パス）をn －1回行います。
　整列の作業を最後まで行わずに、1パスだけ行った時点でのデータの並びがどうなるかが問われています。n が6である場合を、以下に示します。
１パス目 ┌─┬─┬─┬─┬─┬─┐ │５│４│１│３│６│２│ 最初の状態 └─┴─┴─┴─┴─┴─┘ └─┘ ↓ 比較して交換。 ┌─┬─┬─┬─┬─┬─┐ │４│５│１│３│２│６│ └─┴─┴─┴─┴─┴─┘ └─┘ ↓ 比較して交換。 ┌─┬─┬─┬─┬─┬─┐ │４│１│５│３│２│６│ └─┴─┴─┴─┴─┴─┘ └─┘ ↓ 比較して交換。 ┌─┬─┬─┬─┬─┬─┐ │４│１│３│５│２│６│ └─┴─┴─┴─┴─┴─┘ └─┘ ↓ 比較するが交換はしない。 ┌─┬─┬─┬─┬─┬─┐ │４│１│３│５│２│６│ └─┴─┴─┴─┴─┴─┘ └─┘ ↓ 比較して交換。 ┌─┬─┬─┬─┬─┬─┐ │１│４│３│５│２│６│ └─┴─┴─┴─┴─┴─┘ ※１パスが終了した時点で、最小値が配列の先頭A[1]に位置します。