修了試験 2013-07-28実施分 基本情報技術者試験 問5

解説

正解は4です。 代表的な整列（ソート）アルゴリズムの名称と手順の対応を問う問題です。 この問題の選択肢1〜3は、手順の説明は正しいものの、名称が別のアルゴリズムと入れ替わっています。 【選択肢別解説】 1：× 一定間隔おきの要素を整列し、間隔を詰めていく方法は、クイックソートではなくシェルソートの説明です。 2：× 隣り合う要素を比較して逆順なら交換する方法は、シェルソートではなくバブルソートの説明です。 3：× 基準値（ピボット）より大きい区分と小さい区分に振り分け、各区分で同じ処理を繰り返す方法は、バブルソートではなくクイックソートの説明です。 4：○ ヒープソートの説明として正しい記述です。 未整列部分をヒープ（親が子より大きい、または小さい順序木）に構成します。 根から最大値または最小値を取り出して既整列部分に移す操作を繰り返します。 【ポイント】 平均計算量は、クイックソートとヒープソートがO(n log n)、バブルソートがO(n^2)です。 クイックソートは最悪の場合にO(n^2)になる点もあわせて覚えましょう。