選択ソート【selection sort】基本選択法

概要

数値の列を先頭から小さい順（昇順）に並べる場合を考える。まず、先頭から末尾までの間で最も小さい値を見つけ、先頭の値と交換する。次に2番目から末尾までの間で最も小さい値を見つけ、2番目の値と交換する。

以降も同様に、「n番目から末尾までで最も小さい値を見つけ、n番目と入れ替える」という操作を繰り返す。これを末尾の一つ前の値まで繰り返せば、先頭が最も小さく末尾が最も大きい数値の列が得られる。

列の元の状態によらず O（n²） の計算量がかかるため処理時間の予測はしやすいが、ソートアルゴリズムの中では最も遅いものの一つに分類される。木構造の一種である二分ヒープ木を用いて改良した手法を「ヒープソート」（heap sort）という。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート（内部ソート）で、同じ大きさの要素の順序の維持は保証されない不安定ソートである。挿入ソートなどと同じように、アルゴリズムの理解や実装が容易なため、対象データ列が短いことが分かっている場合などに利用されることがある。