導入
挿入ソートは古典的なソート アルゴリズムであり、その原理は非常に単純です。これは、ほとんどの人がカードを分類するために自然に使用する並べ替えです。シャッフルされたカードを 1 枚ずつテーブルから取り出し、各カードを所定の位置に挿入してハンドを形成します。
一般に、挿入ソートは漸近複雑さが二次関数であるため、大規模なシーケンスを処理する場合のクイックソートやマージソートなどの他のアルゴリズムよりもはるかに遅くなります。
ただし、挿入ソートは、小さな入力に対して最も効率的なソートであると考えられています。データがすでにほぼソートされている場合も非常に高速です。これらの理由から、実際には、クイックソート (またはクイックソート) などの他のメソッドと組み合わせて使用されます。
コンピューター プログラミングでは、この並べ替えはテーブルに適用されることが最も多いです。以下のアルゴリズムの説明と検討はこのバージョンに限定されますが、リストへの適応については後で検討します。
アルゴリズムの説明
このアルゴリズムでは、ソート対象の配列を最初から最後まで調べます。 i番目の要素を検討する時点で、その要素に先行する要素はすでにソートされています。カード ゲームの例で例えると、旅のi番目のステップにいるとき、 i番目の要素は入力されたカードで、前の要素はソートされた手札で、次の要素はカードに対応します。まだテーブルの上でシャッフルされています。
ステップの目的は、 i番目の要素を、先行する要素の中でその位置に挿入することです。これを行うには、他の要素と比較して要素を挿入する場所を見つけ、挿入を実行できるように要素をオフセットする必要があります。実際には、これら 2 つのアクションは 1 つのパスで実行されることが多く、これは、より小さい要素に遭遇するまで要素を徐々に「上に移動」することで構成されます。
以下は、提示されたアルゴリズムの疑似コードの説明です。テーブルTの要素には 0 からn -1 までの番号が付けられます。
プロシージャ sort_insertion(array T, integer n) for i from 1 to n - 1 x:= T[i] j = i (j > 0 および T[j - 1] > x T[j] = T[j) - 1] j = j - 1; T[j] = x
挿入ソートは、安定したソート (等しい要素の出現順序を保持) であり、インプレース ソート (補助配列を使用しません) です。
複雑
挿入ソートの複雑さは、最悪の場合および平均で Θ( n2 ) であり、最良の場合では線形です。より正確には:
- 配列が逆方向にソートされるときに到達する最悪のケースでは、アルゴリズムは約n 2 /2 の代入と比較を実行します。
- 要素が個別であり、それらの順列がすべて等しい可能性がある場合、アルゴリズムは平均して約n 2 /4 回の割り当てと比較を実行します。
- 配列がすでにソートされている場合、 n-1 回の比較と O( n ) 回の代入が行われます。
配列がほぼソートされている場合 (たとえば、各要素が本来あるべき位置から制限された距離にある場合、または制限された数値を除くすべての要素が所定の位置にある場合)、挿入ソートの複雑さは線形のままです。この特定の状況では、挿入ソートは他のソート方法よりも優れたパフォーマンスを発揮します。たとえば、マージソートとクイックソート（ピボットランダム化を使用）は両方とも
