アルゴリズム２
◆　クイックソート

　ソート対象の配列をランダムで基準値というものを決め（だいたい最大と最小の中間的な値を取るみたいですが、基準値の決め方は特に決まっていないようです。）、 基準値の大きい集合と小さい集合と入れ替えを繰り返す、再帰的なソートです。
　例として以下のデータがあり、基準値を「15」にしようと思います。

2 5 6 3 10 9 8 15 12 18 27 21

　次は「15」より下を左に、「15」以上を右に入れ替えます。 なので下の図だと「15」と「12」が入れ替わります。

2 5 6 3 10 9 8 12 　 15 18 27 21

　今度は更に２つ分かれた集合で、基準値を決めます。今度は左側を「7」、右側を「20」としましょう。

2 5 6 3 　 10 9 8 12 　 15 18 　 27 21

　上の図では入れ替わるデータは無かったので、分かれるだけです。
　更に各集合体で基準値を決めます。　・・・と言う風に繰り返して最終的にソートされるやり方です。
集合を分割していくので分割統治方と言われて、過去問題でも意味を問われる事が多いみたいです。

　いろいろあるソートの手法の中では一番速くできる手法だと言われてます。
　ちなみに計算量は平均では O ( n log2 n )です。


◆　マージソート

　データを分割するというのはクイックソートに似ているかも知れませんが、クイックソート違って基準値がなく、半分からわけていくやり方みたいです。
　下が例です。

2 7 12 5 9 18 13 21 3 10

↓

2 7 12 5 9 　 18 13 21 3 10

↓

2 7 　 12 5 　 9 　 18 13 　 21 3 　 10

　上の様に、データを２つ以下まで分割します。
　今度これをマージしていきます。この時に同時にソートを行います。

2 7 　 12 5 　 9 　 18 13 　 21 3 　 10

↓

2 7 　 5 9 12 　 18 13 　 3 10 21

↓

2 5 7 9 12 　 3 10 13 18 21

↓

2 3 5 7 9 10 12 13 18 21

　過去問題でも意味を問われる事が多く、午後でも問題が出る事があります。
　ちなみに計算量は平均では O ( n log2 n )です。


TOPページに戻る