主にソートされた配列をソートする方法
1. 序章
このチュートリアルでは、4つの標準を分析します ソートアルゴリズム ほとんどソートされた入力配列でどれが最適に機能するかを確認します。
2. 問題文
並べ替えに関しては、通常、最悪の場合または平均的な場合に関心があります 複雑 アルゴリズムの。 複雑さの分析に基づいて、使用するアルゴリズムを選択します。
ただし、一般的なケース分析は、当面のアプリケーションには適さない場合があります。 入力配列がほとんどソートされている場合、つまり、その要素のごく一部だけが順序どおりになっていない場合、複雑度の低いアルゴリズムは、理論的に優れたアルゴリズムよりもパフォーマンスが向上する可能性があります。
ここでは、すでにほとんどがソートされている（昇順）の4つのソートアルゴリズム整数配列のパフォーマンスを分析します。 配列の要素を整数インデックスにマップできるため、このように一般性を失うことはありません。 唯一の仮定は、インデックスが一意であるため、分析された配列内のオブジェクトも一意であるということです。 したがって、分析は重複のあるアレイには適用されませんが、繰り返し回数が少ないアレイでも同様の結果が期待できます。
3. 方法論
まず、ほとんどソートされた配列を定義する必要があります。 次に、そのような配列をシミュレートし、選択した並べ替えアルゴリズムのパフォーマンスを比較します。
3.1. 主にソートされた配列
配列のほとんどが故障している場合、配列はソートされていると言えます。より正確には、このような配列は次の条件を満たす。
(1)
ここで、はほとんどソートされている度合いであり、は配列をそのように見なすためのしきい値です。 またはのような小さな値に設定すると、「ほとんどソートされた」の定義を満たすのは、より少ない要素またはソートされていない要素を持つ配列のみです。
式（ 1 ）の反転からペアを呼び出します。 これから説明するように、いくつかの確率モデルを使用して反転を作成できます。これにより、ほとんどが並べ替えられたさまざまなタイプの配列を区別できます。
3.2. 主にソートされた配列のタイプ
以下の4種類を検討しました。
左摂動配列は、左側の部分に反転を含む配列です。 言い換えれば、反転の確率は左から右に指数関数的に低下します。 したがって、反転のインデックス（）は、CDFを使用した幾何分布に従います。 を見つけるために、次のようなインデックスの前に転倒が発生するという条件を課します。
これは、両方のインデックスが反転で従う実際の分布ではありません。 その理由は、反転であるということです。 したがって、最初のインデックスに上記の幾何分布を使用し、とは異なる数が得られるまで繰り返し描画します。 同じことが他のタイプにも当てはまります。
同様に、右摂動配列には、その右部分に反転が含まれています。 対応する分布のCDFは、左摂動アレイのCDFです。
中央で摂動された配列では、反転は中央の要素の周りにあります。正式には、の間の質量を含むガウス分布でインデックスをモデル化します。 したがって、分布の平均はであり、前述の条件からの標準偏差を取得します。
最後に、均一に摂動されたアレイの反転は、任意の位置で発生する可能性があります。 対応する分布はで均一です。
3.3. アルゴリズム
バブルソート、挿入ソート、クイックソート、マージソートの4つのアルゴリズムを分析しました。
最初の2つは、その動作方法のために選択されました。 私たちは、それらが私たちのアレイでうまく機能するだろうと思った。 マージソートは、経験的に検証したかった最悪の場合でも、対数線形の時間計算量を持っています。 クイックソートは最悪の場合は2次式である可能性がありますが、平均的な場合であるため、データをどのように処理するかに関心がありました。
3.4. パフォーマンスメトリクス
並べ替えアルゴリズムの複雑さは、通常、比較とスワップの観点から表されます。そのため、両方の操作をカウントするアルゴリズムを実装しました。
ただし、どちらが安いかという明確なルールはありません。 オブジェクトがfloat、chars、integersなどの軽量の場合、スワップにはいくつかの手順が含まれるため、よりコストのかかる操作になると予想されます。 一方、オブジェクトは非常に複雑な場合があります。 したがって、それらを比較すること自体が複雑なアルゴリズムになる可能性があります。 そのような場合、複雑さを決定するのは比較の数です。
したがって、分析では比較とスワップの両方を考慮します。 実行時間も測定しました。 ただし、これらの結果は確固たるものではありません。 異なるハードウェアおよびオペレーティングシステムでの異なる実装は、実行時間が異なる場合があり、おそらく異なるでしょう。
4. 結果
スワップ、比較、および実行時間（秒単位）の結果を個別に表示します。
4.1. スワップの数
入力配列に含まれる要素と反転が多いため、すべてのアルゴリズムでスワップが多くなりました。
バブルソートの結果は次のとおりです。
均一に摂動されたアレイでより多くのスワップを実行します。
結果は挿入ソートでも同様です。
一方、摂動タイプはクイックソートのパフォーマンスに影響を与えないようです。
その理由は、そのソートロジックが異なるためです。 パーティショニング中にほとんどの作業を実行します。 そこでは、スワップの数は主に選択されたピボットに依存します。 マージソートについても同様です。
それでも、バブルソートと挿入ソートは、要素を含む配列で最も少ないスワップを実行したようです。
4.2. 比較の数
結論はスワップの数と同様です。増加し、比較の数も増加しました。 ただし、クイックソートとマージソートは、に関係なく、すべてのタイプで安定しているように見えます。 バブルソートと挿入ソートは、均一に摂動されたアレイでパフォーマンスが低下しました。 全体として、比較の数だけを考慮すると、挿入ソートが最良のオプションのように見えます。
バブルソートの結果を調べてみましょう。
挿入ソートでも同様の結果が得られます。
マージソートの結果は、スワップの数とほぼ同じです。
最後に、クイックソートについても同じことが言えます。
4.3. 実行時間
実行時間のプロットを見てみましょう。 バブルソートが配列をソートするのにかかった時間は次のとおりです。
均一に摂動されたアレイは、他のタイプよりも困難でした。 結論は、より高速であったことを除いて、挿入ソートについても同様です。
マージソートはさらに高速で、要素のある配列と要素の違いがより顕著になりました。
クイックソートはマージソートと同様に動作しました。
比較とスワップの数が一貫して少ないため、挿入ソートが最適なアルゴリズムであると結論付ける傾向があったかもしれません。 ただし、プロットからわかるように、クイックソートとマージソートのアルゴリズムが最速でした。
結果の正確性にはかなり自信があるかもしれませんが、実行時間はアルゴリズムの実行だけに依存するわけではないことに注意してください。ハードウェアとソフトウェアの環境、および同時に実行されている他のプログラムが結果に影響を与えている可能性があります。
5. 結論
このチュートリアルでは、すでにほとんど並べ替えられている配列の並べ替えについて説明しました。 バブルソート、挿入ソート、クイックソート、マージソートの4つの標準的なソートアルゴリズムをテストしました。それらのパフォーマンスを推定するために、4種類のほとんどソートされた配列を生成し、スワップと比較の数をカウントしました。実行時間を測定しました。
全体として、挿入ソートは私たちの実験で最も少ないスワップと比較を行ったようですが、最速のアルゴリズムはクイックソートとマージソートでした。したがって、結果は、クイックソートとマージソートが最良の平均ケースの時間計算量であり、最悪の場合でも後者が最適です。
それでも、これは経験的な研究であったため、異なるアレイで複製すると異なる結果が得られる可能性があることに注意する必要があります。 それが実証研究の本質です。
