ソート2

4.マージソート

数列を分割していき最終的に１つの要素まで分割した後、２つの要素同士を併合させていきソートするアルゴリズム。 

何せ計算速度が高速であり、最悪計算速度はクイックソートに勝る(アベレージでは遅れを取るが)

膨大な乱数を取り扱う時に有用である。

5.クイックソート

名前の通り最強最速のソート

データの比較と交換回数が他に比べて少なく、1回のループが少ない手順で済む。

以下アルゴリズム分析

1.何らかの方法で、軸要素を生成

(一般的にはランダムで抽出した要素の中間値を軸要素とする)

2.軸要素を2分割するしきい値として利用

3.分割された数列の先頭から軸要素より高い要素を検出し、それぞれを交換する。

4.括られた数列の中で同様の処理を繰り返す。

これらを再帰的に繰り返す事で降順に整列される。

ソート1

「ソート(整列)なんて片っ端から昇順か降順でやれば良いじゃん？」って思っている方、これはナンセンス。情報系のデベロッパたるもの常にアルゴリズムを意識しなくてはなりません。

ここでは基本何たら試験に出題されるソートのアルゴリズムを何個か紹介していきます。

1.バブルソート

これは隣合った数字と自分の数字の大小を比較し整列するアルゴリズム。

1回のループで数字が1つ定まる。

最悪計算時間が長いが単純な仕組み、また並列演算との親和性が高いため実装が楽。

2.選択ソート

これは配列から最小値を取る要素をサーチしそれを配列の先頭に置く、以後この繰り返しを行うアルゴリズムである。また、初めの最小値には配列の先頭値を振り込んでおく。

バブルソートと違い、全体から要素を抽出して並び替えていくものである。

選択対象の値をインデックスで保持し、その値と比較しながら洗っていくので各ループの最大交換数は1回であるのでバブルソートより高速。

3.挿入ソート

ソート済みのインデックスに新たな要素を追加するアルゴリズム

番兵等で効率化も図れるが基本何たら試験の管轄外なので割愛

ソート済みの情報量が少ないほど高速なのでクイックソートの仕上げに使われることがよくある。

アルゴリズムを分析すると、クイックソートで分割した整列を挿入ソートで組み立てる。簡単やな

そろそろ面倒になってきたから4からは次の記事で