アルゴリズム (全70問中48問目)

No.48

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

〔アルゴリズム〕
行番号
  1. iを1からn−1まで1ずつ増やしながら行2〜3を繰り返す
  2. jをnからi+1まで減らしながら行3を繰り返す
  3. もしA[j]<A[j−1]ならば,A[j]とA[j−1]を交換する
  • A[1]が最小値になる。
  • A[1]が最大値になる。
  • A[n]が最小値になる。
  • A[n]が最大値になる。

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

例として"7315"の文字列(n=4)を用いて整列の流れを考えてみましょう。
  1. 行1:1から(4-1=)3まで増やしながら繰り返す。
  2. 行2:i=1,4から(1+1=)2まで減らしながら繰り返す。
  3. 行3:j=4,A[4]とA[3]を比較。5<1は成立しないので、交換はしない。[7315]
  4. 行3:j=3,A[3]とA[2]を比較。1<3が成立するので、A[3]とA[2]交換する。[7135]
  5. 行3:j=2,A[2]とA[1]を比較。1<7が成立するので、A[2]とA[1]交換する。[1735]
ここまでで行2〜3の処理の1回目の処理が終了しました。処理の結果、文字列の中で最小値である"1"が配列の先頭(A[1])に格納されていることが確認できます。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop