最小値を探すソートアルゴリズム「単純選択法」とは?

  • 2016/08/09 14:42:35
目次
  • 1:単純選択法のアルゴリズム
  • 2:単純選択法の利点と欠点

単純選択法はあまり計算効率の良いソートアルゴリズムではないのですが、仕組みが簡単なので実装が簡単である利点があります。

単純選択ソートとも呼ばれます。

単純選択法のアルゴリズム

今回の例では以下の数値の配列をソートしたいものとします。

ks1

単純選択法のアルゴリズムのキモは最小値を探すことです。

まず配列の中から最小値を探します。例の配列では2が最小値になるかと思います。

そして見つかった最小値を配列の先頭に移動します。言い換えると未ソート領域の先頭と入れ替えるということになります。

現段階ではどの数字もソートされておらずすべてが未ソート領域なので、未ソート領域の先頭は8です。

すると配列は以下のようになります。

ks3

この時2はすでにソートが済んだ数値なのでソート済み領域とします。

今度はこの配列からソート済み領域の2を除いた中で最小値を探します。ここでは7が最小値になりますね。

ks4

先ほどと同じように未ソート領域の先頭と入れ替えをします。ここでは13が未ソート領域の先頭になります。

入れ替えを行うとこのようになります。

ks5

これを続けると…

ks6

ks7

ks8

ks9

ks10

このように昇順(小さい値から大きい値順)でソートすることができました。もし降順(大きい値から小さい値順)にしたいなら最大値を探すようにすれば降順ソートが可能になります。

単純選択法の利点と欠点

単純選択法は紹介したとおりに、最小値(最大値)を探して入れ替えるという極めて単純なソート方法です。そのため理解しやすく、プログラミングに落としこむ時に初心者でも容易に実装できる利点があります。

しかし、このアルゴリズムはすべての値を最後まで入れ替える(入れ替えが発生しないとしても)必要があるので配列の要素が多い場合は時間がかかってしまう欠点もあります。

またこの単純選択法は安定ソートではありませんので、多次元配列で同値を含むデータのソートには向いていない場合があります。