基本情報技術者試験「整列アルゴリズムの特性」の問題
シェルソートの基本的な考え方を最も適切に説明したものはどれか。
ア配列を中央で二分し各半分を整列した後に順序を保って併合する操作を繰り返す
イ基準値より大小に分割する操作を再帰的に適用する
ウ一定間隔で離れた要素群を挿入ソートし、間隔を徐々に縮める
エ親が子より大きい木を構成し根を順に取り出して並べる
正解
ウ．一定間隔で離れた要素群を挿入ソートし、間隔を徐々に縮める
シェルソートはまず大きな間隔で離れた要素同士を挿入ソートし、間隔(ギャップ)を段階的に小さくして最後に間隔1で仕上げる。遠くの要素を早く移動でき挿入ソートを高速化するため正しい。
?選択肢ごとの解説
ア ×中央で二分し併合するのはマージソートの説明であり、間隔を縮める挿入の考え方とは異なる。
イ ×基準値で大小に分割し再帰するのはクイックソートの説明であり、シェルソートの手法ではない。
ウ ○シェルソートはまず大きな間隔で離れた要素同士を挿入ソートし、間隔(ギャップ)を段階的に小さくして最後に間隔1で仕上げる。遠くの要素を早く移動でき挿入ソートを高速化するため正しい。
エ ×親が子より大きい木(ヒープ)を作り根を取り出すのはヒープソートの説明である。
✎くわしく
シェルソートは挿入ソートの『遠距離移動が苦手』という弱点を、大きな間隔の整列で早期に粗く並べることで補う。計算量はギャップ列の選び方に依存し、平均でO(n^1.3)程度まで改善できるが不安定ソートである。
✓本番での押さえどころ
試験のコツ
代表ソートの一言要約を固定: マージ=分割併合、クイック=基準で分割、ヒープ=木で取り出し、シェル=間隔つき挿入。
覚え方
シェル=貝殻の渦のように間隔を外側から内側へ縮める、とギャップ縮小を連想する。
よくある誤り
マージ(分割併合)・クイック(分割再帰)・ヒープ(木構造)と混同しやすい。シェルは『間隔つき挿入ソート』と押さえる。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 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-a3-0135