読者です 読者をやめる 読者になる 読者になる

まぐとろ

中卒が難関国立を目指してみるブログ。勉強内容メインたまに趣味

ソートは奥が深いんだぞ2

4.マージソート

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

f:id:X86:20170413090655p:image

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

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

 

5.クイックソート

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

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

以下アルゴリズム分析

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

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

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

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

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

 

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