挿入ソートの計算量の証明

参考：https://www.youtube.com/watch?v=JcNyaB_GKe0

[3,4,2,5,6,1]という配列を考える。このとき挿入ソートを行うと、

1回目で[3]を整列済みとすると[3,4,2,5,6,1]となる。

2回目で[3,4]が整列済みとなり値は変化しないので[3,4,2,5,6,1]となる。

3回目で[3,4,2]が整列済みとなり、[2,3,4]となるので、配列は[2,3,4,5,6,1]となる。

4回目、5回目は配列が変化しないので省力する。

6回目では[2,3,4,5,6,1]が整列済みとなり、[1]が一番最初にくるため、配列は[1,2,3,4,5,6]となる。

この例を踏まえると、整列済みの対象が増えれば増えるほど、値は比較する回数が増えていくことがわかる。そのため、[5,4,3,2,1]のように、すべての整列済みの場合において比較をする必要があるとき、計算量はオーダー記法で示すと

1+2+3+...(n-2)=(n-1) = (n^2-n)/2 → O(n^2)

となる。