テクノロジ系出題頻度 3/3
選択ソート
せんたくそーと
定義
未整列部分から最小値を選び先頭に置く操作を繰り返すソート法。計算量O(n²)。
詳細解説
未整列部分から最小値を線形探索し、先頭要素と交換する操作を n−1 回繰り返す。常にO(n²)で入力に依存しない。比較回数は多いが交換回数はO(n)と少ないため、要素移動のコストが高い場合に有利。安定ソートではない（同値要素の順序が崩れうる）。バブルソートと並ぶ基本アルゴリズムで、概念学習用。実用的にはクイックソートやマージソートが用いられる。
「選択ソート」が出る問題
関連用語
よくある質問
Q. 選択ソートとは何ですか？
A. 未整列部分から最小値を選び先頭に置く操作を繰り返すソート法。計算量O(n²)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。