選択ソート
以下、ソートする配列の要素数を n とする。
要素の比較に関して、各ループで n − 1 回、n − 2 回、......と行われ、処理全体としては ∑ k = 1 n − 1 k = n ( n − 1 ) 2 {\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}} 回行われる。
要素の交換に関して、各ループで最大1回行われ、処理全体では多くとも n − 1 回となる。
バブルソートと比較すると、要素の比較回数は同じだが交換回数が少ないため、選択ソートの方が高速である。
選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。
最良時間計算量は O(n) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。
選択ソートは内部ソートである。また、安定ソートではない。
選択ソートの改良として、ヒープソートが挙げられる。