高度情報処理技術者試験・情報処理安全確保支援士試験 令和3年度 秋期 午前I 問3

【正解】ウ

バブルソートは、隣り合う二つの要素を順番に比較し、大小関係が目的の順序と逆なら入れ替える操作を繰り返す整列方法です。例えば、昇順に並べるとき、列が「5、2、4」なら、まず5と2を比較して「2、5、4」とし、次に5と4を比較して「2、4、5」とします。列の端まで比較すると最大値が末尾に確定するので、未整列部分を狭めながら同じ処理を繰り返します。要素が泡のように端へ浮かび上がることが名称の由来です。

アは誤りです。これはシェルソートの説明です。一定の間隔で要素を取り出して部分列を整列し、その間隔を徐々に狭め、最後に間隔1で整列します。

イは誤りです。これはクイックソートの説明です。基準値であるピボットを選び、それより小さい要素と大きい要素に分割して、それぞれを再帰的に整列します。

エは誤りです。これはヒープソートの説明です。要素をヒープと呼ばれる順序木に構成し、最大値又は最小値を順次取り出して整列します。

【ポイント】 バブルソートの識別語は「隣り合う要素の比較と交換」です。 平均計算量と最悪計算量はともにO（n²）で、大量のデータには効率的ではありません。 交換条件を適切にすれば、同じ値の元の順序を保つ安定ソートになります。