（１）選択ソート

SortとMergeについて（１）選択ソート

Sort（データを特定の規則で並べる）と　Merge（Sort済データを統合する）はプログラミングの基礎的なロジックです。
Sortの機能はほとんどの言語に用意されていますので、あえてコードを書く必要はないかもしれませんが、そのロジックを理解しておくことは無駄ではないと思います。Mergeはデータがソート済であることが前提なので、先ず基本的な6種類のソートをご紹介したいと思います。

１．基本的なソート

• 選択ソート
  未ソートの中から最小（最大）値を検索して先頭から順番に並び替えていく。
• バブルソート
  両隣のデータを比較して順序が逆なら入れ替える。
  先頭から作業をした場合は、最後尾から順番に最小（最大）値が押しやられる。
• 挿入ソート
  ソート済データ（最初は１件）の中に未ソートのデータを適切な位置に挿入していく。
• マージ＆ソート
  データを半分に分割し、再帰的に小さくしていき、十分小さくなったらMerge（統合）する。
• クイックソート
  基準値を設定しその値より大きいグループと小さいグループに分ける作業を再帰的に繰り返す。
• ヒープソート
  データを2分木の構造（親の下に子が最大２つあるツリー構造）に配置し、下の階層から　ヒープ条件（親 ＞＝ 子、又は、親＜＝子）を満たすように調整すると、最上位の階層の親（ルートノード）に、最大(小)値が移動するので、その後は、最大(小)値を末尾と交換し、残りを再びヒープ化する作業を繰り返す。
  
  次にそれぞれのソート方法をもう少し詳しく説明します。

２．選択ソート

基準値とそれ以降の未ソートのデータを順番に比較して、小さい（大きい）データを基準値と入れ替える作業を最後まで繰り返すと、基準値が最小（最大）値がとなります。基準値の位置を順番にずらしていき、最後に到達すれば完了です。
下図は配列に格納されたデータを、二つのインデックスで回しながらソートしていく様子です。
配列の番号は’０’から起算する言語が多いですが、ここでは’１’から起算しています。

フローチャートは下記のようになります。

選択ソートは最もわかりやすいロジックだと思いますが、データ量が多いと時間がかかります。
また、同じ値を持つデータがあると、もともとの並びと逆になる可能性があるので注意が必要です。

次回は、バブルソートをご説明します。