どの並べ替えアルゴリズムを使用しますか？

1. 概要

このチュートリアルでは、さまざまな並べ替えアルゴリズムと、特定の状況でそれらを使用する目的について説明します。ソートアルゴリズムにはソートの一般的な目的がありますが、それぞれに独自の欠点と利点があります。一部のアルゴリズムは、既存のアルゴリズムに蔓延していた問題を克服しました。

問題は、必要な追加スペース、時間の複雑さ、および複雑なデータや巨大なデータを処理する能力に基づいています。アルゴリズムは、配列、リンクリスト、スタック、キューなどのデータ構造をどのように処理するかに基づいて、それぞれの場合に適用されます。典型的なアプリケーションは、eコマース、データベース管理システム、またはグラフトラバーサルです。

2. 並べ替えアルゴリズム

並べ替えは、要素を順番に並べるプロセスです（通常は昇順）。特定の要素を検索する必要があるアプリケーションには、整理されたデータが必要です。このセクションでは、さまざまな並べ替えアルゴリズムとその複雑さについて説明します。

2.1. マージソート

マージソートは、ジョンフォンノイマンによって発明され、分割統治法に従って要素の数をソートします。まず、各グループが単一の値になるまで、値は同じサイズのグループ（要素を含むその反復の各グループ）に繰り返し分割されます。次に、要素は分割プロセスとは逆の方法でマージされます。マージは、反復ごとに、マージされたグループ内のデータを徐々に並べ替えます。最後に、ソートされた要素のセットを生成します。

マージソートは、連続してアクセスされるデータ構造に適しています。テープドライブは、CPUが順番にデータにアクセスできる最良の例です。また、インバージョンを使用してユーザーの関心を追跡するために、eコマースの分野でも使用されます。

マージソートは、データに関係なく同じ完全なプロセスを実行します。時間計算量の最良、平均、および最悪のケースは、ソートされた要素の数です。スペースの複雑さは、追加のスペースのためであり、リンクリストを使用して実装する場合です。

データは、反復ごとに個別のリストにコピーされます。したがって、特に大きなデータセットの場合、配列には適していません。挿入に余分なスペースが必要ないため、リンクリストの方が適しています。

2.2. バブルソート

バブルソートは、Iversonによって使用されるようになった最も単純なソートアルゴリズムの1つです。昇順ではありません。このプロセスは、完全にソートするためのさまざまな反復で行われます。反復が進むにつれて、リストは最後の要素から順番に下降し始めます。

小さいリストは、ソートを完了するのに必要な単純さのために、バブルソートを使用してソートします。コンピュータグラフィックスでは、ポリゴン塗りつぶしアルゴリズムで線の座標を順番に並べるために使用されます。

並べ替えられたリストの場合、時間計算量の最良のケースはです。平均および最悪の場合は、であり、最悪の場合の状況は降順の要素です。最悪のシナリオでは、ペアの最大数がスワップして、反復ごとに最後に到達します。バブルソートは、ソートアルゴリズムと小さな要素セットの基本的な理解のために引き続き使用されます。

2.3. 選択ソート

選択ソートは、最小要素を見つけて値を置き換えることによって進行するソート手順です。アルゴリズムは、最初の場所のアイテムからの比較から始まります。他の位置に小さい値が存在するかどうかを確認するために他の人とチェックされます。はいの場合、要素を交換し、最初の場所に最小の番号を配置するようにします。

たとえば、最初の場所の要素は、その右側の各要素に対してチェックされます。が他のどの要素よりも小さい場合は、その場所に残ります。それ以外の場合は、とスワップし、残りの要素と比較されます。この手順は、最終的に要素のソートされた順序を示します。

アルゴリズムはすべての場所のすべての要素を比較するため、選択ソートの時間計算量はです。一方、スペースの複雑さはです。小さなアイテムのセットでより速くソートされます。バブルソートと同じように、ソートの概念を学ぶのに役立ちます。

2.4. クイックソート

Quicksort は、Tony Hoareによって開発された、分割統治法を使用した別の並べ替え方法です。 アルゴリズムは、選択されたピボット番号（並べ替えプロセス全体で同じ位置）に基づいて要素を繰り返し分割します。単一の要素を持つグループに到達するまで、サブグループに対してこれを継続的に実行します。このメソッドは、ピボット数よりも小さいか大きいかに応じて、グループを2つのサブグループに分割します。

最良の平均的な時間計算量はです。最良のケースは、毎回中央値であるピボット番号を選択することです。

最悪のケースは、選択されたピボット番号が毎回最小または最大の番号である場合です。この状態は、要素が昇順または降順でソートされている場合に発生する可能性があります。最悪の場合の時間計算量はです。

このソート方法のスペースの複雑さはです。クイックソートはそれほど余分なスペースを必要としませんが、より大きなデータセットにはそれほどお勧めできません。

クイックソートは、プライマリメモリの一部ではないが、プロセスの実行中はメモリスペースのように見える仮想環境でより高速に動作します。これは、場所に基づいて要素にアクセスしやすく、追加のストレージを必要としないアレイに適しています。

2.5. ヒープソート

JWJ ウィリアムズメソッドを開発しましたヒープソート、二分木構造を構築することによって要素をソートします。ツリー形式には、最大ヒープツリーと最小ヒープツリーの2種類があります。親ノードが子ノードよりも大きい場合、それは最大ヒープツリーと呼ばれます。親ノードが子ノードよりも小さい場合、それは最小ヒープツリーと呼ばれます。

ヒープソートは、ヒープ化、スワップ、および挿入という3つの主要なアクションによって進行します。

ヒープ化中、ツリーは、新しいノードが挿入されるたびに、ツリーが最大ヒープまたは最小ヒープのツリー構造を満たしているかどうかがチェックされます。
ツリーがヒープ形式になった後、最初の要素が最後のビットと交換されます
最後に、更新されたツリーの終了要素をソートされた出力リストに挿入します

これらの3つのステップは、ルートノードが残り、出力リストに挿入されてソートされた要素を取得するまで繰り返し続けられます。

セキュリティを必要とするシステムと組み込みシステムはヒープソートを使用します。通常、要素をソートするために同じ手順を実行するため、すべての場合で時間計算量はです。

スペースの複雑さはであるため、リンクリストの並べ替えに適しています。ヒープソートの複雑さは、要素が増えると対数的に増加するため、巨大なデータセットに適しています。

2.6. 挿入ソート

挿入ソートは、 JohnMauchlyによって導入された単純な反復ソート方法です。 挿入ソートは、比較、移動、配置の3つのステップに従います。

挿入ソートは、すべての反復で1つのアイテムを後続のアイテムと比較し、手順は次のとおりです。

要素は、その後継がそれよりも大きいかどうかを比較します
はいの場合、そのままになり、後続要素が隣接要素とチェックされます。
それ以外の場合、要素は1つ上の位置に移動し、挿入用のスペースを提供します
連続する要素がその前の要素と比較され、リスト内の正しい位置に配置されている間
配置中、アイテムは、その前のアイテムがより少ない位置に配置されます

時間計算量の最悪の平均的なケースは、すべての要素がソートされたリストを作成するために移動し、残りのビットが毎回シフトする場合です。最良のシナリオは、それがソートされたリストであり、時間計算量がである場合です。そして、挿入ソートのスペースの複雑さはです。挿入ソートは、小さなデータセットと、大きなデータセット内のほぼソートされたリストに使用できます。

2.7. イントロソート

DavidMusserによって発明されたIntrosortは、個別の並べ替え手法を持たないハイブリッド並べ替えアルゴリズムですが、その並べ替え戦略により注目に値します。 イントロソートの主な機能は、データセットに基づいて挿入ソート、クイックソート、ヒープソートのいずれかを選択することです。

各ソートアルゴリズムには、長所と短所があります。イントロソートは、データセットに応じて適切な並べ替えアルゴリズムを使用します。挿入ソートはマイナーデータが多いほど良いので、そのようなデータをソートします。ピボット要素が中央値を見つけることによって得られる中間値である場合、クイックソートは適しています。また、ヒープソートは、反復が高くなるときに使用されます。それでも、イントロソートには、データを配列に入れることができないという主な欠点があります。