アルゴリズム(全80問中58問目)
No.58解説へ
配列A[i](i＝1，2，…，n)を，次のアルゴリズムによって整列する。行2～3の処理が初めて終了したとき，必ず実現されている配列の状態はどれか。
〔アルゴリズム〕
行番号
〔アルゴリズム〕
行番号
- iを1からn－1まで1ずつ増やしながら行2～3を繰り返す
- jをnからi＋1まで減らしながら行3を繰り返す
- もしA[j]＜A[j－1]ならば，A[j]とA[j－1]を交換する
出典：平成19年春期 問14
- A[1]が最小値になる。
- A[1]が最大値になる。
- A[n]が最小値になる。
- A[n]が最大値になる。
広告
解説
例として"7315"の文字列(n＝4)を用いて整列の流れを考えてみましょう。
- 行1:1から(4-1=)3まで増やしながら繰り返す。
- 行2:i＝1，4から(1+1=)2まで減らしながら繰り返す。
- 行3:j＝4，A[4]とA[3]を比較。5＜1は成立しないので、交換はしない。[7315]
- 行3:j＝3，A[3]とA[2]を比較。1＜3が成立するので、A[3]とA[2]交換する。[7135]
- 行3:j＝2，A[2]とA[1]を比較。1＜7が成立するので、A[2]とA[1]交換する。[1735]
広告