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

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

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

(単純・基本)選択ソート法とは、次のようにして、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番目の要素を交換する。

【計算コスト】選択ソートの計算時間

比較回数は、「n(n-1)/2」、「交換回数」は、各ループで最大1回なので、最悪回数はn-1回。
よって、最悪計算時間がO(n^2)ですが、バブルソートと比較すると、「交換回数」が少ないので、選択ソートの方が高速となります。

【プログラミング】選択ソートの実装

プログラミング言語で選択ソートを実装する方法については、言語別に下記事で紹介しています。

メディアを追加

詳細記事
1 【Python】選択ソート法(交換法)を実装
おすすめ記事
1 【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
2 【情報処理入門】テクノロジ系、マネジメント系、ストラテジ系、資格試験
コンピュータ
技術雑記

コメント

タイトルとURLをコピーしました