クイックソート対。マージソート
1. 序章
データを並べ替えるアルゴリズムはたくさんあります。 通常、並べ替えアルゴリズムを選択するときは、速度やスペース使用量などの基準に依存します。
このチュートリアルでは、2つの一般的な並べ替えアルゴリズムQuicksortとMergesortを比較します。 どちらのアルゴリズムも、分割統治アプローチをさまざまな方法で適用し、パフォーマンスとストレージの使用に関してもさまざまなプロパティを適用します。
2. クイックソート
クイックソートは、分割統治法を適用する一般的なインプレース並べ替えアルゴリズムです。 クイックソートを3つの主要なステップに要約できます。
- ピボットとして要素を選択します
- 小さな要素をピボットの左側に移動し、大きな要素をその右側に移動して、問題セットを分割します
- ソートされたリストに到達するまで、各パーティションで上記の手順を繰り返します
クイックソートを使用して次のリストを並べ替える小さな例を見てみましょう。
最初のステップは、ピボットを選択することです。 ピボットを選択する方法はいくつかありますが、この例では、常に右端の要素を選択します。
ピボット23を選択したら、23より大きいすべての要素を右に移動し、23より小さいすべての要素を左に移動する必要があります。
これにより、リストを2つのパーティションに分割しました。
これで、各パーティションでアルゴリズムの手順を繰り返すことができます。 右端のパーティションは1つの要素のみで構成されているため、左端のパーティションに手順を適用できます[15、3、8、10。 5]ピボットとして5を選択し、その周りの要素を整理します。 これを行った後、ソートされたセットに徐々に近づいていることに注意してください。
これで、[5]の周りに2つのパーティションができました。これらは[3]で、これ以上パーティションを作成する必要はありません。[15,8,10]です。 ピボットとして10を選択し、残りの15と8をその周りに整理することで、最終的なソート済みリストに到達します。
クイックソートのより詳細な説明と、ピボットを選択するさまざまな方法については、クイックソートの概要記事を読むことができます。
次に、マージソートを同じ配列に適用して、それがどのように機能するかを見てみましょう。
3. マージソート
マージソートは、もう1つの分割統治アルゴリズムです。 ただし、クイックソートとは異なり、インプレースアルゴリズムではなく、ソートされたサブ配列を格納するために一時配列が必要です。
マージソートは2つの主要なステップに要約できます。
- 1つの要素に到達するまで、リストをサブリストに分割します
- 最終的なソート済みリストに到達するまで、サブリストをソート済みサブリストに繰り返しマージします
ここで、前の例で使用したのと同じ配列に概念を適用してみましょう。 ソートされていないリストから始めて、リストを最小のサブリストに分割します。
次に、2つのサブリストをそれぞれ取得してマージし、マージされたサブリストがソートされていることを確認します。 これで、4つのソートされたサブリストができました。
ここでも、2つのサブリストをそれぞれ取得し、それらをマージしてソートされたサブリストにします。これにより、2つのソートされたサブリストが得られます。
最後に、同じ概念をもう一度適用します。これにより、最終的にソートされたリストが得られます。
マージソートアルゴリズムとその実装方法のより詳細な概要については、リンクリストにマージソートがどのように適用されるかを説明するこの記事を参照してください。
4. マージソートとクイックソートの比較
クイックソートとマージソートがどのように機能するかがわかったので、これら2つのアルゴリズムの主な違いを見てみましょう。
5. 結論
この記事では、QuicksortとMergesortの2つの並べ替えアルゴリズムについて説明しました。
これらのメソッドが実際にどのように機能するかを学び、スペース、時間の複雑さ、および安定性やインプレースソートなどの他のプロパティの観点からそれらを比較しました。
