クイックソートとマージソートの主な違いは、クイックソートが各要素とピボットと呼ばれる要素を比較してソートするのに対し、マージソートは配列を2つのサブ配列に分割し、1つの要素が残るまで何度も繰り返し行う点です。
ソートとは、データを特定の順序に並べる方法です。
データを並べる際には、数値順や辞書順を考慮することが可能である。
ソートは、データ要素の検索やアクセスをより速く、素早く行うのに役立つ。
ソートには様々なアルゴリズムがあり、クイックソートとマージソートはその一つです。
クイックソートとは
クイックソートは、「分割統治法」を用いた内部アルゴリズムです。
分割交換ソートとも呼ばれます。
配列内の要素の比較と分割に、ピボットと呼ばれるキー要素を使用します。
ピボットより小さい値を持つ項目はピボットの左側に、ピボットより大きい値を持つ項目はピボットの右側に移動します。
左側の区画を左分割、右側の区画を右分割と呼ぶ。
以下の例を参照してください。
36 34 43 11 15 20 28 45 27 32
32をピボットとし、36と27を考える。
36 < ピボット、27 > ピボットという条件は偽です。
したがって、この2つの値を入れ替えればよいことになります。
これで、リストは次のようになります。
27 34 43 11 15 20 28 45 36 32
34と45の値について考えてみましょう。
34 < pivotを考えると、条件は偽となります。
同様に、45＞ピボットの条件は真です。
さて、45から28に移動することができます。
34と28を考えてみましょう。
34 < pivot は偽で、28 > pivot も偽です。
よって、34と28を入れ替えることができます。
27 28 43 11 15 20 34 45 36 32
43と20を考えてみましょう。
43＜ピボットは偽。
20 > ピボットは偽。
よって、この2つの数字を入れ替えることができます。
これで、リストは次のようになります。
27 28 20 11 15 43 34 45 36 32
ここで、11と15を考えてみましょう。
11 < pivot は真です。
15を考えてみましょう。
これは32より小さいです。
これは重なり合う点であり、次のように32を配置することができます。
27 28 20 11 15 32 43 34 45 36
これで、ピボットの左側にある数字はピボットより小さく、ピボットの右側にある数字はピボットより大きくなりました。
左右のパーティションにクイックソートを適用して、リスト全体をソートすることができます。
マージソートとは
マージソートは、「分割統治法」を利用した外部アルゴリズムです。
配列を2つのセクションに分割します。
それぞれの配列をソートし、それらを結合してソート済み配列を形成します。
マージソートは、補助的な配列をソートするために追加のストレージを必要とします。
次の例で考えてみよう。
図2: マージソート
配列を2つに分割することができます。
38 27 43 3 9 82 10
38 27 43 3 を考えてみましょう。
これを再び2つの配列に分割することができます．38 27と43 3です。
38 27は38と27に分割され、43 3は43と3に分割されます。
38と27を並べ替えると27 38となります。
43 3 を並べ替えると、3 43 になります。
ここで、27 38と3 43を組み合わせることができる。
27 38と3 43の組み合わせは可能です。
同様に、9 82 10を考えてみましょう。
9 82と10です。
9 82は9と82に分割されます。
さらに、もう一方の配列には10番があります。
9と82は9 82としてソートされます。
最後に、3 27 38 43 と 9 10 82 が組み合わされ、ソートされた配列が得られます。
クイックソートとマージソートの違い
定義
クイックソートは効率的なソートアルゴリズムで、配列の要素を順番に並べるための体系的な方法として機能します。
これに対して、マージソートは効率的で汎用的な比較ベースのソートアルゴリズムです。
これがクイックソートとマージソートの根本的な違いです。
機能性
クイックソートとマージソートの大きな違いは、なんといってもその機能です。
クイックソートは各要素をピボットと比較してソートし、マージソートは配列を2つのサブアレイ（n/2）に分割し、1つの要素が残るまで何度も繰り返します。
アプリケーション
また、クイックソートは小さい配列に適していますが、マージソートはどのような配列にも対応します。
速度
クイックソートとマージソートのもう一つの違いは、クイックソートが小さなデータセットに対して高速に動作するのに対し、マージソートはすべてのデータセットに対して一定の速度で動作することである。
必要なスペース
さらに、クイックソートとマージソートの重要な違いとして、必要なスペースが挙げられます。
クイックソートはマージソートに比べて最小限のスペースしか必要としない。
効率性
さらに、クイックソートは大きな配列に対して効率が悪いのですが、マージソートはクイックソートより効率が良いです。
この点もクイックソートとマージソートの違いと言えるでしょう。
結論
まとめると、クイックソートとマージソートの大きな違いは、クイックソートが各要素とピボットと呼ばれる要素を比較してソートするのに対し、マージソートは1つの要素が残るまで配列を2つの部分配列に何度も分割してソートする点です。
