問題プレビューID: c6ad5f2e基本情報技術者試験 午前免除試験 2012年7月22日

問 6
基本情報技術者試験 午前免除試験 2012年7月22日

配列 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] を交換する
解説

正解は「ア」です。

このアルゴリズムは,隣り合う要素を比較して大小が逆ならば交換する操作を,配列の後ろから前へ向かって繰り返すバブルソート(昇順整列)です。

初回の外側の繰り返し(i=1)では,j を n から 2 まで減らしながら,A[j] と A[j−1] を比較して A[j] の方が小さければ交換します。これにより小さい値が順に前方へ移動していき,行 2〜3 が初めて終了した時点で,配列中の最小値が A[1] に移動しています。

したがって「ア」が正解です。

  • イ・エ: 大きい値は前方(A[1] 側)へは集まらず,A[1] が最大値になることはありません。A[n] に最大値が確定するのは,この整列の途中の別の段階です。
  • ウ: 最小値は A[1] 側へ移動するため,A[n] が最小値になることはありません。

関連問題

本文が同じ・似ている問題を表示しています