【基本情報技術者試験平成19年春期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

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

問14　　 整列アルゴリズム

　配列 A[ i ]（ i ＝1，2，...， n ）を，次のアルゴリズムによって整列する。行２～３の処理が初めて終了したとき，必ず実現されている配列の状態はどれか。

〔アルゴリズム〕

　行番号

　　１　 i を１から n －１まで１ずつ増やしながら行２～３を繰り返す

　　２　　 j を n から i ＋１まで減らしながら行３を繰り返す

　　３　　　もし A[ j ] ＜ A[ j －１] ならば，A[ j ]とA[ j －１] を交換する

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

ウ　A[ n ] が最小値になる。　　　　エ　A[ n ] が最大値になる。

解説

　問題のアルゴリズムは、基本交換法（バブルソート）である。バブルソートの考え方は単純で隣り合うデータを比較し、大小関係が逆のとき入れ換えを行い、入れ換えが起こらなくなるまでこれを繰り返す方法である。このアルゴリズムは、データがある程度整列されているときに効率がよい。

　行２～３の処理が初めて終了したとき、A[ 1 ] が最小値になる。