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

解説

正解は1です。 代表的な整列（ソート）アルゴリズムの動き方と名前を対応させる問題です。 クイックソートは、基準値（ピボット）による分割を繰り返す方式です。 【選択肢別解説】 1：○ 基準となる要素を選び、それより大きい集合と小さい集合に分割する操作を再帰的に繰り返すのがクイックソートです。 平均計算量はO(n log n)で、高速な整列法として知られます。 2：× 未整列部分から最小の要素を順に選んで取り出すのは選択ソートです。 3：× 取り出した要素を整列済みの集合の正しい位置に挿入していくのは挿入ソートです。 4：× 隣り合う要素を比較して逆順なら交換するのはバブルソート（交換法）です。 【ポイント】 「分割」はクイック、「最小を選ぶ」は選択、「挿入」は挿入、「隣と交換」はバブルと、動作のキーワードで覚えます。 クイックソートは、ピボットの選び方が悪いと最悪O(n²)になる点も出題されます。