問題プレビューID: 52244d4b基本情報技術者試験 午前免除試験 2022年6月12日

問 9
基本情報技術者試験 午前免除試験 2022年6月12日

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

〔アルゴリズム〕

行番号処理
1ii を 1 から n−1n-1 まで 1 ずつ増やしながら行 2〜3 を繰り返す
2jj を nn から i+1i+1 まで 1 ずつ減らしながら行 3 を繰り返す
3もし A[j]<A[j−1]A[j] < A[j-1] ならば,A[j]A[j] と A[j−1]A[j-1] を交換する
解説

正解は「ア」です。

このアルゴリズムは基本交換法(バブルソート)の一種です。i=1i = 1 のとき,jj を nn から i+1=2i+1 = 2 まで 1 ずつ減らしながら,隣り合う要素 A[j]A[j] と A[j−1]A[j-1] を比較し,A[j]<A[j−1]A[j] < A[j-1] ならば交換します。jj を大きい方から小さい方へ動かすことで,小さい値が次々と前へ移動し,行 2〜3 の処理が初めて終了した時点で最小値が A[1]A[1] に移動します。したがって「ア」が正解です。

  • イ: 最大値が確定するのは,この並びでは最終段階(i=n−1i = n-1 付近)であり,最初のパスではありません。
  • ウ: A[n]A[n] に移動するのは最大値であり,最小値ではありません。
  • エ: 最初のパスが終了した時点で A[n]A[n] が最大値になるとは限りません。

関連問題

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