【選択ソート法とは】リストの昇順・降順ソートの原理と計算量

（単純・基本）選択ソート法とは？リストを昇順・降順ソートする原理・アルゴリズムについて解説します。

[latexpage]

【選択ソート法とは】リストを昇順・降順ソート

（単純・基本）選択ソート法とは、次のようにして、N個のデータをもつリストの要素を、繰り返し最小値（降順なら最大値）を抽出して整列させるアルゴリズムです。

順序	操作
①	最悪計算時間がO(n^2)と計算時間が大きい（低速）。
②	仕組みが単純なので実装しやすい。

昇順ソートを行う場合は以下の操作を行います。

順序	操作
①	1番目～N番目の要素のうち、最小値をもつ要素を1番目の要素と入れ替える。
②	2番目～N番目の要素のうち、最小値をもつ要素を2番目の要素と入れ替える。
：	：
③	N-1番目～N番目の要素のうち、最小値をもつ要素をN-1番目の要素と入れ替える。

※降順ソートの場合は「最小値」が「最大値」となる。

理解を深めるために、3つの要素をもつリスト[7, 3, 5]の昇順ソートを選択ソート法で行ってみます。

リストの状態	操作
[7, 3, 5]	1番目～3番目の要素のうち、最小値をもつ要素を抽出する。（2番目の要素「3」が最小）
[3, 7, 5]	1番目と2番目の要素を交換する。
[3, 7, 5]	2番目～3番目の要素のうち、最小値をもつ要素を抽出する。（3番目の要素「5」が最小）
[3, 5, 7]	2番目と3番目の要素を交換する。