基本情報技術者 一問一答｜B 第203問

解説

選択ソートの1パス目は、配列全体から最小値を探し、それを先頭の要素と交換する。{5,3,8,1,4}では、全要素を走査して最小値1（4番目）を見つけ、先頭の5と交換するため、結果は{1,3,8,5,4}で正解である。交換によって元の先頭にあった5が、1のあった位置に移る点に注意する。{3,5,8,1,4}は隣接要素を交換するバブルソートの動きと混同した誤り、{1,3,4,5,8}はソート完了後の最終状態であり1パスでは到達しない。{5,3,8,1,4}は交換を行わなかった場合である。頻出ポイントは①選択ソートは「最小値を選んで先頭から確定」、バブルソートは「隣接比較で末尾に最大値が確定」という確定位置の違い、②選択ソートの交換回数は各パス最大1回と少ないが、比較回数はO(n²)のままであること、の2点である。