選択ソート 【selection sort】 基本選択法 / セレクションソート / 単純選択法

概要

選択ソート（selection sort）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの最も基本的な手法の一つで、未整列の要素の中から最大あるいは最小のものを選択し、整列済みの列の末尾に追加していくもの。

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

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

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

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

(2024.3.7更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる