導入
ソート アルゴリズムは、コンピュータ サイエンスまたは数学において、オブジェクトのコレクションを特定の順序で整理できるようにするアルゴリズムです。したがって、並べ替えられるオブジェクトは、順序関係 (通常は全体の順序) を持つセットの一部です。最もよく使用される順序は、数値順序と辞書編集 (辞書) 順序です。
考慮される順序関係に応じて、オブジェクトの同じコレクションからさまざまな配置が生じる可能性がありますが、使用される順序関数とは独立して並べ替えアルゴリズムを定義することができます。これは、コレクション内の要素の任意のペアを比較できるようにする順序関係に対応する特定の順序関数のみを使用します。
分類
ソートアルゴリズムの分類は、それによって課せられる制約を考慮しながら、対処する問題に最適なアルゴリズムを選択できるため、非常に重要です。
まず第一に、要素のペア間の比較によって進行する一般的なアプリケーションのソート アルゴリズムと、入力データの構造について限定的な仮説を立てるより特殊なアルゴリズム (たとえば、データが取得された場合にのみ適用できるカウントによるソートなど) を区別します。事前に知られている小さなセットから）。何も指定しない場合、通常、「並べ替えアルゴリズム」とは、比較による一般的な並べ替えアルゴリズムを意味します。
ソート アルゴリズムの差別化を可能にする主な特徴は、アルゴリズムの複雑さ、必要なリソース (特に使用されるメモリ領域の点)、および安定した性質です。
アルゴリズムの複雑さ
- 最悪の場合のアルゴリズムの時間計算量により、 n個の要素のセットを並べ替えるのに必要な操作の数に上限を設定することができます。
- アルゴリズムの平均時間計算量: これは、要素のコレクションを並べ替えるために平均して実行される基本操作の数です。これにより、並べ替えアルゴリズムを比較でき、アルゴリズムに必要な実行時間についての適切なアイデアが得られます。かなり高い精度で推定できます。ただし、ソートされるセットが特定の形状を持ち、 n !を表していない場合は、可能な組み合わせを組み合わせた場合、パフォーマンスは「平均的な」複雑さよりもはるかに低い、またははるかに高い可能性があります。
- 空間アルゴリズムの複雑さ (平均または最悪の場合) は、アルゴリズムが必要とするメモリ使用量を表します。これは、実行時間と同様に、並べ替える要素の数に依存する可能性があります。
一般にTで表される複雑さは、ランダウ表記OおよびΘ を使用して要素の数nの関数として表されます。最も単純な並べ替えアルゴリズムの一部の場合は T( n ) = O( n 2 )、より複雑な並べ替えアルゴリズムの場合は T( n ) = O( n ·log( n )) です。
比較関数に基づくアルゴリズムの平均時間計算量と最悪の場合の時間計算量は、 n ·log( n )よりも優れているはずがないことがわかります。平均してn ·log( n ) 回の比較のみを必要とする並べ替えは、最適と呼ばれます。
ソート問題は、完全に順序付けられた集合(例:
連続的な比較による並べ替えアルゴリズムはバイナリツリーとしてモデル化され、ツリーの各ノードはセットの 2 つの要素間の比較に対応します。 2 つの要素uとu を比較し、結果に応じて次の 2 つのノードのいずれかに移動し、そこで別の比較を実行します。ツリーの各リーフ(終端ノード) は、完全にソートされたシーケンスに対応します。
アルゴリズムは、シーケンスの項の置換の可能性をすべて提供できなければなりません。これは、置換 σ を提供することと、ソートされたシーケンスy を提供することと同等であるためです。 n個の要素の順列の数はn ! (n 階乗) ツリー上の葉の数は少なくともn でなければなりません。 。
最悪の場合の複雑さの下限
h がツリーの最大の深さを表すものとします (最悪の場合のステップ数について話しています)。最大深さhの二分木の最大葉数は2 hです。
したがって、次のようになります。
種類があるという事実
平均的な複雑さの下限
二分木Aが与えられた場合、 Aの葉の平均深さをF ( A ) で表します。入力要素のすべての順列の可能性が等しい場合、比較ツリーAとのソートの比較の平均数はF ( A ) に等しくなります。
固定数のノードの場合、 Fを最小化するツリーは完全な 2 分ツリー (つまり、葉がすべて最後または最後から 2 番目のレベルにあるもの) です。実際、不完全なツリーAには、深さhの葉と最大でも深さh -2 の葉が存在します。最初の葉を2 番目の葉に接続すると、 F ( A’ ) < F ( A ) となる木A’ が得られます。
関数F は、 n ! を含むすべての完全なバイナリ ツリーで同じ値を持ちます。葉、 A をそのうちの 1 つとして、その高さに注目してみましょう。すべての葉の深さは少なくともh -1 であるため、葉の平均深さは少なくとも
ただし、特定の種類のデータ (整数、サイズが制限された文字列) については、カウント ソートや基数によるソートなど、実行時間の点でより効率的なアルゴリズムがあります。これらのアルゴリズムは要素間の比較を使用しません (したがって、 n・log(n)限界はそれらに適用されません) が、並べ替えられるオブジェクトについての仮定を必要とします。たとえば、カウント ソートと基数によるソートは、セット [1, m ] に属することがわかっている整数に適用されます。基数によるソートでは、 m が2 の累乗(c ‘、つまり 2 の形式である) という追加の仮定が適用されます。 k )。
所定の位置にあるキャラクター
アルゴリズムは、非常に限られた数の変数のみを使用し、並べ替えている構造を直接変更する場合に、適切に配置されていると言われます。これには、適切なデータ構造 (テーブルなど) を使用する必要があります。使用可能なメモリが大量にない場合、この文字は非常に重要になります。
ただし、一般に、データ自体を直接並べ替えるのではなく、データへの参照 (またはポインタ) のみを並べ替えることに注意してください。
安定した性格
アルゴリズムは、順序関係において等しい量の相対順序を維持する場合に安定していると言われます。
たとえば、次の一連の要素を考えてみます。
(4, 1) (3, 1) (3, 7) (5, 6)
最初の座標 (キー) に基づいて並べ替えると、相対順序が尊重される場合とそうでない場合の 2 つのケースが考えられます。
(3, 1) (3, 7) (4, 1) (5, 6) (相対順序維持) (3, 7) (3, 1) (4, 1) (5, 6) (相対順序変更)
2 つの要素の順序関係が等しい (つまり、同じキーを持つ) 場合、並べ替えアルゴリズムは、これら 2 つの要素が実行される前の順序を維持します。不安定な並べ替えアルゴリズムを安定させるために特別に再加工することはできますが、これにより速度が犠牲になったり、追加のメモリ領域が必要になったりする可能性があります。
以下に挙げるアルゴリズムの中で安定しているソートは、バブル ソート、挿入ソート、マージソートです。他のアルゴリズムでは、要素の初期順序を保存するために O(n) 個の追加メモリが必要です。