基本情報技術者試験「整列」の問題
次の手続 onePassAsc は、配列 arr に対して隣接交換を 1 パス行い、最大値を末尾へ送る（昇順整列の 1 パス）ことを意図している。arr = {5, 2, 8, 1}（要素数 4、添字は 1 から）に対して実行したとき末尾 arr[4] が 8 になるよう、空欄 [ a ] に入れる条件式として適切なものはどれか。
○手続: onePassAsc(整数型の配列: arr)
整数型: k, tmp
for (k を 1 から arrの要素数 − 1 まで 1 ずつ増やす)
if ( [ a ] )
tmp ← arr[k]
arr[k] ← arr[k + 1]
arr[k + 1] ← tmp
endif
endforアarr[k] < arr[k + 1]
イk < k + 1
ウarr[k] ≠ arr[k + 1] かつ k > 0
エarr[k] > arr[k + 1]
正解
エ．arr[k] > arr[k + 1]
昇順整列の隣接交換では、左の要素が右より大きいときに入れ替える。arr[k] > arr[k+1] とすると最大値 8 が末尾に押し出され arr[4]=8 となるため エが正しい。
?選択肢ごとの解説
ア ×arr[k] < arr[k+1] は左が小さいとき交換する降順の条件で、最小値 1 が末尾へ送られ arr[4]=1 となる、不等号の向きを逆にした誤りである。
イ ×k < k + 1 は添字どうしの比較で常に真となり、毎回無条件に交換するため要素が掻き混ぜられ arr[4]=5 となる誤りである。
ウ ×arr[k] ≠ arr[k+1] かつ k > 0 は『隣が異なれば常に交換』となり、大小に関係なく入れ替えて arr[4]=5 となる、比較条件の取り違えである。
エ ○昇順整列の隣接交換では、左の要素が右より大きいときに入れ替える。arr[k] > arr[k+1] とすると最大値 8 が末尾に押し出され arr[4]=8 となるため エが正しい。
✎くわしく
バブルソートの 1 パスは比較条件の不等号の向きが昇順・降順を決める。> なら大きい方が後ろへ（昇順）、< なら小さい方が後ろへ（降順）移動する。
✓本番での押さえどころ
試験のコツ
『昇順は大きいものを後ろへ＝左が大きければ交換＝>』と対応づける。
覚え方
『昇順の泡は大きいほど上（末尾）へ＝>』と覚える。
よくある誤り
不等号の向きを逆にして降順になる、または値でなく添字を比較してしまうミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0168