「選択ソート」の版間の差分

削除された内容 追加された内容
編集の要約なし
8行目:
|space=''О(n)'' total, ''O(1)'' auxiliary
|optimal=No
}}'''選択ソート'''({{lang-en-short|selection sort}})は、[[ソート]]の[[アルゴリズム]]の一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間が[[ランダウの記号|O]](n<sup>2</sup>)と遅いが、非常に直感的で単純なアルゴリズムが単純あり、実装容易なため、しばしば用いられる。内部ソート。後述するように、[[安定ソート]]ではない。
 
このアルゴリズムを改良したソート法として、[[ヒープソート]]が挙げられる。
 
==アルゴリズム==
データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する。これを、データ列の最後まで繰り返す(厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後(残り)は必ず最大値になるからである)。大小が入れ替わる[[降順]]の場合も同様の手法である。また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、'''double selection sort'''と呼ばれる。
 
===実装例===
<syntaxhighlight lang="text">
150 ⟶ 151行目:
: '''1 2 3 4 5 6''' 7 8 (6回目のループ終了時)
: '''1 2 3 4 5 6 7 8''' (7回目のループ終了時)
 
 
==計算時間==