修了試験 2015-06-28実施分 基本情報技術者試験 問6

解説

正解は3です。 代表的な整列（ソート）アルゴリズムの処理方法を見分ける問題です。 【選択肢別解説】 1：× 整列済みの列の正しい位置にデータを挿入していく方法は、挿入ソート（基本挿入法）です。 クイックソートではありません。 2：× 最小値を選んで取り出す操作を繰り返す方法は、選択ソート（基本選択法）です。 3：○ クイックソートの説明です。 基準値（ピボット）を選び、それより小さいグループと大きいグループに分割し、各グループで同じ分割を繰り返します。 分割統治の考え方で、平均の計算量はO(n log n)です。 4：× 隣り合ったデータの比較と交換を繰り返す方法は、バブルソート（基本交換法）です。 【ポイント】 「基準値で分割」ならクイックソート、「隣同士を交換」ならバブルソートです。 クイックソートは平均では高速ですが、基準値の選び方が悪いと最悪O(n^2)になる点も覚えておきましょう。