ソート技法、クイックソートおよびマージソートの両方とも、要素のセットを分割してから並べ替え後に結合するという分割統治方式に基づいています。 クイックソートは通常、要素の大きなセットをソートするためにマージソートよりも多くの比較を必要とします。
比較表
| 比較基準 | クイックソート | ソートのマージ |
|---|---|---|
| 配列内の要素の分割 | 要素のリストの分割は、必ずしも半分に分割されるわけではありません。 | 配列は常に半分（n / 2）に分割されます。 |
| 最悪の場合の複雑さ | O（n2） | O（n log n） |
| うまくいく | 小さい配列 | どんなタイプの配列でも問題なく動作します。 |
| 速度 | 小さなデータセットのための他のソートアルゴリズムよりも高速です。 | すべての種類のデータセットで一貫した速度。 |
| 追加の保管スペース要件 | もっと少なく | もっと |
| 効率 | 大規模な配列には非効率的です。 | もっと効率的な。 |
| ソート方法 | 内部 | 外部 |
クイックソートの定義
クイックソートは、短い配列に対して高速であるため、広く使用されているソートアルゴリズムです。 要素の集合は、それ以上分割できなくなるまで繰り返し部分に分割されます。 クイックソートはパーティション交換ソートとも呼ばれます 。 要素を分割するためにキー要素（ピボットと呼ばれる）を使用します。 1つのパーティションには、キー要素よりも小さい要素が含まれています。 別のパーティションには、キー要素より大きい要素が含まれています。 要素は再帰的にソートされます。
Aがソートされなければならないn個の数の配列A [1]、A [2]、A [3]、……..、A [n]であると仮定します。 クイックソートアルゴリズムは以下のステップで構成されています。
- キーとして選択された最初の要素または任意のランダム要素は、キー= A（1）と仮定します。
- "low"ポインタは2番目に配置され、 "up"ポインタは配列の最後の要素に配置されます。つまり、low = 2とup = nです。
- 一貫して、（A [low]>キー）まで「low」ポインタを1つずつ増やします。
- 常に、（A [up] <= key）まで「up」ポインタを1つ減らす。
- upがlowより大きい場合、A [low]とA [up]を入れ替えます。
- ステップ5の条件が満たされなくなるまで（つまりup <= low）ステップ3、4、および5を繰り返してから、A [up]をキーと交換します。
- キーの左側の要素がキーよりも小さく、キーの右側の要素がキーよりも大きい場合、配列は2つのサブ配列に分割されます。
- 上記の手順は、配列全体がソートされるまでサブアレイに繰り返し適用されます。
長所と短所
それは良い平均ケースの振る舞いを持っています。 クイックソートの実行時の複雑さは優れています。つまり、バブルソート、挿入ソート、選択ソートなどのアルゴリズムよりも高速です。 しかし、これは複雑で非常に再帰的であるため、大規模な配列には適していません。
マージソートの定義
マージソートは、分割統治戦略にも基づく外部アルゴリズムです。 要素は、1つの要素だけが残るまで何度も何度もサブ配列（n / 2）に分割されます。これによりソート時間が大幅に短縮されます。 補助配列を格納するために追加の記憶域を使用します。 マージソートは3つの配列を使用します。2つは各半分を格納するために使用され、3つ目は最終的なソート済みリストを格納するために使用されます。 その後、各配列は再帰的にソートされます。 最後に、サブ配列をマージして、配列のn要素サイズにします。 リストは、クイックソートとは異なり、常に半分（n / 2）に分割されています。
Aをソートするn個の要素の配列A [1]、A [2]、………、A [n]とします。 マージソートは与えられたステップに従います。
- 配列Aを2で約n / 2のソートされたサブ配列に分割します。つまり、（A [1]、A [2]）、（A [3]、A [4]）、（A [ ｋ］、Ａ ［ｋ ＋ １］、（Ａ ［ｎ − １］、Ａ ［ｎ］）サブアレイはソートされた順序でなければならない。
- ペアの各ペアを組み合わせて、サイズ4のソートされたサブアレイのリストを取得します。 部分配列の要素もソート順になっています（A [1]、A [2]、A [3]、A [4]）、……、（A [k-1]、A [k]、A ［ｋ ＋ １］、Ａ ［ｋ ＋ ２］、……、（Ａ ［ｎ − ３］、Ａ ［ｎ − ２］、Ａ ［ｎ − １］、Ａ ［ｎ］）。
- サイズnのソート済み配列が1つだけになるまで、ステップ2が繰り返し実行されます。
長所と短所
マージソートアルゴリズムは、ソートに含まれる要素の数に関係なく、まったく同じ方法で正確に動作します。 大規模なデータセットでも問題なく動作します。 ただし、それはメモリの大部分を消費します。
クイックソートとマージソートの主な違い
- マージソートでは、配列は2つの半分（つまりn / 2）に分割されなければなりません。 反対に、簡単に言うと、リストを等しい要素に分割することを強制する必要はありません。
- クイックソートの最悪の場合の複雑さはO（n2）です。最悪の条件ではより多くの比較が必要になるためです。 対照的に、マージソートは同じ最悪ケースと平均ケースの複雑度、すなわちO（n log n）を持ちます。
- マージソートは、大小にかかわらず、あらゆるタイプのデータセットでうまく機能します。 それどころか、クイックソートは大規模なデータセットではうまく機能しません。
- 小さなデータセットの場合など、場合によってはクイックソートの方がマージソートよりも高速です。
- マージソートでは、補助配列を格納するための追加のメモリスペースが必要です。 その一方で、クイックソートは追加のストレージ用のスペースをあまり必要としません。
- マージソートはクイックソートよりも効率的です。
- クイックソートは、ソートされるデータがメインメモリで一度に調整される内部ソート方法です。 逆に、マージソートは、ソートされるデータを同時にメモリに格納することができず、補助メモリに保持する必要がある外部ソート方法です。
結論
クイックソートは速いケースですが、状況によっては効率が悪く、マージソートと比べて多くの比較を実行します。 マージソートでは比較が少なくて済みますが、追加の配列を格納するために0（n）の追加メモリスペースが必要ですが、クイックソートではO（log n）のスペースが必要です。
