(単純・基本)選択ソート法とは?リストを昇順・降順ソートする原理・アルゴリズムについて解説します。
[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番目の要素を交換する。 |
【計算コスト】選択ソートの計算時間
比較回数は、「n(n-1)/2」、「交換回数」は、各ループで最大1回なので、最悪回数はn-1回。
よって、最悪計算時間がO(n^2)ですが、バブルソートと比較すると、「交換回数」が少ないので、選択ソートの方が高速となります。
【プログラミング】選択ソートの実装
プログラミング言語で選択ソートを実装する方法については、言語別に下記事で紹介しています。
– | 詳細記事 |
---|---|
Pythonで実装 | Pythonで選択ソート法(交換法)を実装した例を紹介します. |
【アルゴリズム】整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計
整列、併合、探索、再帰、文字列処理、流れ図の理解、アルゴリズム設計についてまとめました。
【情報処理入門】用語解説・資格試験対策まとめ
情報処理分野の用語・原理・資格試験対策について解説します。
コメント