令和4年度 秋期 午前 問6
アルゴリズム
ここで用いられる整列アルゴリズム
未整列の配列 A[i]（i＝1, 2, …, n）を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。
〔流れ図〕
開始
↓
ループ1 i：1, 1, n−1 （注）
↓
ループ2 j：n, −1, i＋1 （注）
↓
判断 A[j] ： A[j−1]
├─ ≧ のとき ──────────┐（何もしないでループ2の終端へ）
└─ ＜ のとき │
w ← A[j] │
A[j] ← A[j−1] │
A[j−1] ← w │
↓ ←──────────────────────┘
ループ2（終端）
↓
ループ1（終端）
↓
終了
（注）ループ端の繰返し指定は，変数名：初期値，増分，終値 を示す。- アクイックソート
- イ選択ソート
- ウ挿入ソート
- エバブルソート
答えと解説を見る
✓ これが正解エバブルソート
解説
隣り合う 2 つを比べて入れ替える整列です。
設問は、流れ図で示された整列アルゴリズムの名前を選ばせています。軸になるのは 2 点だけです。比べている相手は隣どうしか、そして直し方は入れ替えか、それとも取り出して挿し込む形かです。内側の繰返しは添字を末尾から前へ 1 ずつ減らしながら回り、配列の j 番目と、その 1 つ手前の要素を比べています。手前の方が大きければ、作業用の変数を経由して 2 つを入れ替えます。要素数 4 の並びで 1 周だけ追うと、小さい値が前へ前へと押し上げられ、1 周ごとに先頭側が 1 つずつ確定していきます。隣り合う要素の比較と入れ替えを繰り返す整列なので、答えはバブルソートです。
ほかの選択肢はなぜ違うのか
- アクイックソート：基準となる値で並びを 2 つに分け、分けた先で同じ手順を繰り返す整列です。この流れ図には分割も、自分自身を呼び直す仕組みも現れないので、入口の時点で当てはまりません。
- イ選択ソート：まだ並べ終えていない範囲から最小の値がある位置を探し、1 周につき 1 回だけ入れ替える整列です。この流れ図は条件が成り立つたびに入れ替えるため、1 周で何度も入れ替えが起きます。
- ウ挿入ソート：取り出した値を、入る場所が見つかるまで作業用の変数に保持し続ける整列です。この流れ図の作業用変数は 1 回の入れ替えで使い切られており、値を持ち続ける動きがありません。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：令和4年度 秋期 応用情報技術者試験 午前 問6
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）