サーチ…


備考

ソートアルゴリズムの性能を分析する際には、主に比較と交換の回数に関心があります。

平均取引額

E nを 、N個の要素の配列をソートするための総平均交換回数とする。 E 1 = 0(1つの要素で配列を交換する必要はありません)。 N個の要素配列をソートする平均交換回数は、N-1要素配列に最後の要素を挿入する平均交換でN-1要素配列をソートする平均交換回数の合計です。

ここに画像の説明を入力

総和を単純化する(算術級数)

ここに画像の説明を入力

期間を拡大する

ここに画像の説明を入力

集計を再度簡略化する(算術級数)

ここに画像の説明を入力

平均比較

C nを 、N個の要素の配列をソートするための比較の合計平均数とする。 C 1 = 0(1つの要素配列に対して比較を行う必要はありません)。ソートN要素配列に対する比較の平均数は、N-1要素配列に最後の要素を挿入するために、平均比較でソートN-1要素配列に対する平均比較数の合計です。最後の要素が最大要素である場合、1つの比較のみが必要です。最後の要素が2番目に小さい要素であれば、N-1比較が必要です。しかし、最後の要素が最小要素であれば、N個の比較は必要ありません。私たちはまだN-1の比較しか必要としない。それで、下の方程式で1 / Nを取り除く理由です。

ここに画像の説明を入力

総和を単純化する(算術級数)

ここに画像の説明を入力

用語を展開する

ここに画像の説明を入力

加算を再度単純化する(算術級数と高調波数)

ここに画像の説明を入力

アルゴリズムの基礎

挿入ソートは、非常に単純で安定したインプレースソートアルゴリズムです。小さなシーケンスではうまくいきますが、大きなリストではそれほど効率が悪いです。すべてのステップで、アルゴリズムは、指定されたシーケンスのi番目の要素を考慮し、正しい位置になるまで左に移動します。

グラフィックイラストレーション

挿入ソート

擬似コード

for j = 1 to length(A)
    n = A[j]
    i = j - 1
    while j > 0 and A[i] > n
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = n

以下の整数のリストを考えてみましょう。

[5, 2, 4, 6, 1, 3]

アルゴリズムは、以下のステップを実行する。

  1. [5, 2, 4, 6, 1, 3]
  2. [2, 5, 4, 6, 1, 3]
  3. [2, 4, 5, 6, 1, 3]
  4. [2, 4, 5, 6, 1, 3]
  5. [1, 2, 4, 5, 6, 3]
  6. [1, 2, 3, 4, 5, 6]

C#の実装

public class InsertionSort
{
    public static void SortInsertion(int[] input, int n)
    {
        for (int i = 0; i < n; i++)
        {
            int x = input[i];
            int j = i - 1;
            while (j >= 0 && input[j] > x)
            {
                input[j + 1] = input[j];
                j = j - 1;
            }
            input[j + 1] = x;
        }
    }

    public static int[] Main(int[] input)
    {
        SortInsertion(input, input.Length);
        return input;
    }
}

補助空間: O(1)
時間の複雑さ: O(n)

ハスケルの実装

insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)

insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x    = (n:x:xs)
                | otherwise = x:insert n xs


Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow