クイックソート対。ヒープソート
1. 序章
このチュートリアルでは、QuicksortとHeapsortという2つの強力な並べ替えアルゴリズムを比較します。 クイックソートは高速であるため実際に一般的に使用されますが、メモリ使用量が懸念される場合はヒープソートが使用されます。
まず、クイックソートとヒープソートのアルゴリズムのプロセスについて簡単に説明します。 次に、これらのアルゴリズムを比較し、それぞれの長所と短所について説明します。
2. クイックソート
クイックソートアルゴリズムは、分割統治法に基づいています。 全体として、クイックソートアルゴリズムは3つの主要なステップに従います。
- 配列から要素をピボットとして選択
- Partition 小さな要素をピボットの左側に移動し、大きな要素をピボットの右側に移動することによって設定される問題
- 各パーティションで上記の手順を繰り返します
アプローチをよりよく理解するために、次の図を見てみましょう。
3. ヒープソート
ヒープソートは、バイナリヒープデータ構造に基づく比較ベースのソート方法です。 バイナリヒープ構造により、ヒープソートアルゴリズムはヒープのプロパティを利用できます。
- すべてのノードの値は、その子に格納されているすべての値よりも大きい（または小さい）必要があります
- これは完全なツリーであり、可能な限り最小の高さを持っていることを意味します
ヒープソートを4つの主要なステップに要約できます。
- 入力配列から最小（または最大）ヒープを構築します
- この時点で、最小のアイテムがヒープのルートに格納されます。 ルートノードから要素を削除し、右端の葉をルートノードに保存します。
- Heapifyツリーのルート
- ヒープのサイズが1より大きい場合は、手順2と3を繰り返します。
Heapifyは、ノードがヒーププロパティに従うように、ノードを正しい順序で配置するプロセスです。 ヒープソートアルゴリズムのより詳細な概要とヒープデータ構造の説明については、Javaでのヒープソートと
次に、ヒープソートアルゴリズムの概念を、前の例で使用したのと同じ配列に適用してみましょう。
ヒープソートの時間計算量はすべての場合ですが、ヒープソートは補助スペースを使用するため、メモリの問題が問題になる場合は、ヒープソートが並べ替えアルゴリズムの適切なオプションになる可能性があります。
4. クイックソート対。 ヒープソート
クイックソートとヒープソートがどのように機能するかがわかったので、次の2つのアルゴリズムの基本的なプロパティを比較してみましょう。
これら2つのアルゴリズムの主な違いは、それらの方法にあります。 ヒープソートはヒープデータ構造に基づいていますが、クイックソートは配列を再帰的にパーティション化することで動作します。 各アルゴリズムの主な長所と短所は次のとおりです。
ヒープソートの時間計算量は最悪の場合ですが、ほとんどのマシンでは、適切に実装されたクイックソートよりも実際には遅くなります。 これは、ヒープソートが全体的なパフォーマンスに影響を与える定数要素を隠しているためです。
ただし、ヒープソートは補助スペースのみを使用しますが、クイックソートは最大でを使用するため、組み込みシステムなどでメモリ使用量が制限されている場合は、他のアルゴリズムと比較してヒープソートが適している可能性があります。
クイックソートは、その内部ループをほとんどのアーキテクチャで効率的に実装できるため、実際には高速です。 クイックソートは、最悪の場合を回避するためにピボットの選択を変更することにより、さまざまな方法で実装できます。
さらに、Quicksortは、データがメインメモリで並べ替えられる内部並べ替え方法です。その結果、Quicksortは、メモリに収まらないほど大きいデータセットよりも、小さいデータセットでパフォーマンスが向上します。
5. 結論
この記事では、クイックソートとヒープソートの2つのソートアルゴリズムについて説明しました。
これらの方法がどのように機能するかを学び、それらの基本的な特性を比較し、各アルゴリズムの長所と短所を調査しました。
