選択ソート

Posted on Friday, September 5th, 2014 11:47:48

選択ソートとは

前回のバブルソートに続いて単純なソートアルゴリズムです。配列された要素から、最大値/最小値を探索し、ソートされていない最後の要素とスワップするだけです。

サンプル

ソースプログラム

実行結果

ソート関数の解説

バブルソートと同様、変数 i のループ毎に端っこの要素の値が順に決定していきます。しかし、値が決定するまでの過程がバブルソートと異なります。変数 j のループで決定していない値を順番に舐めていき、昇順であれば最小値、降順であれば最大値を探索します。

配列の最後まで探索し終わったら、その値とソートしていない端っこの要素をスワップ(値の交換)します。これを(要素数 – 1)回繰り返すだけです。つまり、データ数を n とすると、比較回数はバブルソートと同様 (n(n – 1) / 2) になり、計算量は O(n²) です。

ただし、交換回数は毎周の最後に必要であれば最小値/最大値と交換するだけなので、最大(n – 1)回 で済みます。そのため、バブルソートと比べると基本的に高速になります。しかし、安定ソートではありません(同じ値の順序は保証されない)。

まとめると、最小値/最大値のインデックスを保持しておき、ループの最後に1度交換するだけなので、バブルソートに比べると少し高速なのです。ではでは。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です