サーチ…
備考
ソートアルゴリズムの性能を分析する際には、主に比較と交換の回数に関心があります。
平均取引額
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]
アルゴリズムは、以下のステップを実行する。
-
[5, 2, 4, 6, 1, 3] -
[2, 5, 4, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[2, 4, 5, 6, 1, 3] -
[1, 2, 4, 5, 6, 3] -
[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