クイックソートとマージソートの違い

コンテンツ

比較表
クイックソートの定義
マージソートの定義
結論

クイックソートおよびマージソートアルゴリズムは、非常によく似た方法で機能する分割統治アルゴリズムに基づいています。クイックソートとマージソートの以前の違いは、クイックソートではソートにピボット要素が使用されることです。一方、マージソートは、ソートの実行にピボット要素を使用しません。

並べ替え技術、クイックソートとマージソートはどちらも、要素のセットを分割して再配置後に結合する分割統治法に基づいています。通常、クイックソートでは、要素の大きなセットをソートするためにマージソートよりも多くの比較が必要です。

1. 比較表
2. 定義
3. 主な違い
4. 結論

比較表


比較の根拠	クイックソート	ソートをマージ
配列内の要素の分割	要素のリストの分割は、必ずしも半分に分割されるわけではありません。	配列は常に半分（n / 2）に分割されます。
最悪のケースの複雑さ	に²)	O（n log n）
うまくいく	より小さなアレイ	あらゆるタイプの配列で正常に動作します。
速度	小さいデータセットの場合、他のソートアルゴリズムよりも高速です。	すべてのタイプのデータセットで一貫した速度。
追加のストレージスペース要件	もっと少なく	もっと
効率	大きなアレイには非効率的です。	もっと効率的。
選別方法	内部	外部

クイックソートの定義

クイックソート は、短い配列に対して高速であるため、広く使用されているソートアルゴリズムです。要素のセットは、さらに分割できなくなるまで繰り返し部分に分割されます。クイックソートとも呼ばれます パーティション交換ソート。要素を分割するためにキー要素（ピボットと呼ばれる）を使用します。 1つのパーティションには、キー要素よりも小さい要素が含まれます。別のパーティションには、キー要素より大きい要素が含まれます。要素は再帰的にソートされます。

Aがソートされる必要があるn個の配列A、A、A、……..、Aであるとします。クイックソートアルゴリズムは、次の手順で構成されています。

キーとして選択された最初の要素または任意のランダムな要素は、key = A（1）と仮定します。
「low」ポインターは2番目に配置され、「up」ポインターは配列の最後の要素に配置されます。つまり、low = 2およびup = nです。
一貫して、「A」キーまで「ロー」ポインタを1ポジション増やします。
常に、（A <= key）になるまで「上」ポインタを1ポジション減らします。
upがlowとAの交換よりも大きい場合。
手順5の条件が失敗するまで（つまり、up <= low）、手順3、4、および5を繰り返し、Aをキーと交換します。
キーの左の要素がキーよりも小さく、キーの右の要素がキーよりも大きい場合、配列は2つのサブ配列に分割されます。
上記の手順は、配列全体が並べ替えられるまでサブ配列に繰り返し適用されます。

長所と短所

それは良い平均的なケースの動作を持っています。クイックソートの実行時間の複雑さは優れています。つまり、バブルソート、挿入ソート、選択ソートなどのアルゴリズムよりも高速です。ただし、複雑で非常に再帰的であるため、大規模な配列には適していません。

マージソートの定義

ソートをマージ 分割統治戦略にも基づく外部アルゴリズムです。要素は、1つの要素だけが残るまでサブアレイ（n / 2）に何度も分割されます。これにより、ソート時間が大幅に短縮されます。補助配列を保存するために追加のストレージを使用します。マージソートは3つの配列を使用します。2つは各半分の格納に使用され、3つ目の配列は最終的なソート済みリストの格納に使用されます。その後、各配列は再帰的にソートされます。最後に、サブ配列がマージされて、配列の要素サイズがnになります。リストは、クイックソートとは異なり、常に半分（n / 2）に分割されます。

Aを、ソートされるn個の要素の配列A、A、………、Aとします。マージソートは、指定された手順に従います。

配列Aを2で約n / 2のソートされたサブ配列に分割します。つまり、（A、A）、（A、A）、（A、A）、（A、A）サブ配列の要素はソートされた順序である。
ペアの各ペアを組み合わせて、サイズ4のソートされたサブアレイのリストを取得します。サブ配列内の要素も、ソート順（A、A、A、A）、……、（A、A、A、A）、……。、（A、A、A、A）です。
ステップ2は、サイズnのソートされた配列が1つだけになるまで繰り返し実行されます。

長所と短所

マージソートアルゴリズムは、ソートに含まれる要素の数に関係なく、まったく同じ正確な方法で実行されます。大規模なデータセットでも正常に機能します。ただし、メモリの大部分を消費します。

マージソートでは、配列を2つに分割する必要があります（つまり、n / 2）。反対に、クイックソートでは、リストを等しい要素に分割することは強制されません。
クイックソートの最悪の場合の複雑さはO（n²）最悪の状態ではより多くの比較が必要になるため。対照的に、マージソートは同じ最悪のケースと平均のケースの複雑さ、つまりO（n log n）を持ちます。
マージソートは、大小を問わず、あらゆるタイプのデータセットで適切に機能します。それどころか、クイックソートは大きなデータセットではうまく機能しません。
小さいデータセットなどの場合には、クイックソートはマージソートよりも高速です。
マージソートでは、補助配列を保存するために追加のメモリスペースが必要です。一方、クイックソートでは、追加のストレージに多くのスペースは必要ありません。
マージソートは、クイックソートよりも効率的です。
クイックソートは、ソートされるデータがメインメモリで一度に調整される内部ソート方法です。逆に、マージソートは外部ソート方法であり、ソートされるデータを同時にメモリに収容することはできず、一部は補助メモリに保持する必要があります。