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

解説

正解は1です。 クイックソートの手順を問う問題です。 クイックソートは、基準値（ピボット）を選んで集合を分割し、分割を繰り返して整列します。 【選択肢別解説】 1：○ クイックソートの説明です。 基準値より大きい要素と小さい要素に分け、それぞれの集合でも同じ操作を繰り返します。 平均の計算量はn log nのオーダで、高速な整列法として知られます。 2：× 最も小さい要素を順に取り出して整列するのは、選択ソートです。 分割の操作は行いません。 3：× 取り出した要素を、整列済みの集合の正しい位置に挿入していくのは、挿入ソートです。 4：× 隣り合う要素を比較し、逆順なら交換するのは、バブルソート（交換法）です。 【ポイント】 「基準値で分割」はクイックソート、「最小値を選ぶ」は選択ソート、「挿入」は挿入ソート、「隣同士を交換」はバブルソートです。 試験では、記述の動作からアルゴリズム名を選ばせる形がよく出ます。