修了試験 2016-07-24実施分 基本情報技術者試験 問7

解説

正解は4です。 代表的な整列（ソート）アルゴリズムの特徴を問う問題です。 選択肢1〜3は、アルゴリズム名と説明が入れ替わっています。 【選択肢別解説】 1：× 一定間隔ごとの部分列を整列し、間隔を詰めていくのはシェルソートの説明です。 クイックソートは、基準値で要素を大小2つの区分に振り分ける操作を繰り返します。 2：× 隣り合う要素を比較し、逆順なら交換する操作を繰り返すのはバブルソートの説明です。 シェルソートは、離れた間隔の要素同士で整列し、間隔を徐々に小さくする方法です。 3：× 基準値より大きい区分と小さい区分に振り分ける操作を繰り返すのは、クイックソートの説明です。 バブルソートは隣接する要素の比較と交換を繰り返す方法です。 4：○ ヒープソートは、未整列部分をヒープ（親が子以上または以下になる順序木）に構成し、根から最大値または最小値を取り出す操作を繰り返します。 記述はこの手順と一致しています。 【ポイント】 平均計算量は、クイックソートとヒープソートがO(n log n)、バブルソートがO(n^2)です。 「間隔」はシェル、「隣接交換」はバブル、「基準値で分割」はクイック、「順序木」はヒープと結び付けて覚えます。