挿入ソートの解析（アルゴリズム・イントロダクション）

「アルゴリズム・イントロダクション　改訂2版」を読んでいる。
2章の挿入ソートを実装しつつ、ループ不変式や実行時間といったアルゴリズムの正当性に関する考え方がどのようなものかを検討する。

挿入ソートとは

大雑把に言うと、よくある横並びの配列の箱を思い浮かべて、それを左側から順番通りになるよう並び替えていくやりかた。
要素数が少ないか、ほとんど整列されている場合に有効な方法である。また完全に整列されている配列を線形時間O(n)で判定できる。これは他の整列アルゴリズムにはない性質である。（アルゴリズムクイックリファレンスより）

擬似コード(p16)、実装

挿入ソートは以下のINSERTION-SORTという手続きとして与えられる（構文カラーリングはRuby)。

#要素数nとしてnはlength[A]と表記される
INSERTION-SORT(A)
for j ← 2 to length[A]
  do key ← A[j]
    i ← j - 1
    while i > 0 かつ A[i] > key
      do A[i + 1] ← A[i]
         i ← i - 1
    A[i + 1] ← key

これを擬似コードに似せて書くとこうなる（Ruby)。

def insertion_sort(a)
  1.upto(a.length-1) do |j|
    key = a[j]
    i = j - 1
    while i >= 0 and a[i] > key
      a[i+1] = a[i]
      i = i - 1
    end
    a[i+1] = key
  end
  a
end

p insertion_sort([2, 3, 1, 10, 5, 6, 9])
#=>[1, 2, 3, 5, 6, 9, 10]

細かい点であるが、注意すべきなのは、擬似コードでは配列の最初の要素は添字1でアクセスする（A[1]）が、Rubyでは（というか多くのプログラミング言語では）A[0]であるという点だ。
このため、for j ← 2 to length[A]という箇所を1.upto(a.length-1) do |j|として、それ以降のコードも適宜書き換えている。

ループ不変式とは(p16-p17)

さて、挿入ソートのようなアルゴリズムの正しさは、ループ不変式という考え方を導入することにより示すことができる。
擬似コードをもういちど見てみよう。

#要素数nとしてnはlength[A]と表記される
INSERTION-SORT(A)
for j ← 2 to length[A]
  do key ← A[j]
    i ← j - 1
    while i > 0 かつ A[i] > key
      do A[i + 1] ← A[i]
         i ← i - 1
    A[i + 1] ← key

このコードにおけるループ不変式とは次のようなものである。

forループの各繰り返しの頭では、A[1..j]（すなわちA[1]〜A[j]までの配列）は整列されている。

このループ不変式に対して、以下の3つの性質を示すことにより、アルゴリズムの正しさを証明することができる。

初期条件：ループの実行開始直前ではループ不変式は真。
ループ内条件：ある繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である。
終了時条件：ループが終了したとき、ループ不変式からアルゴリズムの正当性を証明できるような性質が得られる。

ある繰り返しの「直前」という表現にちょっともたついたが、これはループの頭ということかな。
この性質はおおまかには以下のように証明される。

初期条件：ループ不変式はA[1]である。要素が一つなのでソート済みであることは明白である。
ループ内条件：A[j]が入れるべき場所が見つかるまでA[j-1],A[j-2],A[j-3],...を右に移し、空いた場所にA[j]を挿入できているかを検討する。厳密にはwhileループ内のループ不変式を検討する必要がある。
終了時条件：ループが終了するのはjが要素数nを超えた時点(n+1)ともいい換えることができる。この時A[1..n]は整列されており、これは配列全体である。配列全体がソートされているため、このアルゴリズムが正当であることが示される。

実行コスト(p22-p24)

実行時間(running time)とは、実行される基本演算またはステップの数である。
伝統的には、実行時間は入力サイズに対してどのように計算時間が増加するかという関数で記述する。
入力サイズ(input size)とは、ここでは配列のサイズnのことである。

さて、実行時間はプログラムの各行の実行時間の合計することによって求める。
各行の実行時間は一行の実行コストと実行回数の積で表される。
各行の実行コストを $c_1$ 〜 $c_7$ として次のように添字を割り振ると。それぞれの行における実行コストと実行回数は以下のようになる。ここで $t_j$ はwhileループの判定がjに対して行われる回数である。

#要素数nとしてnはlength[A]と表記される
INSERTION-SORT(A)                  |COST|        TIMES         |
for j ← 2 to length[A]            | c1 |          n           |
  do key ← A[j]                   | c2 |         n-1          |
    i ← j - 1                     | c3 |         n-1          |
    while i > 0 かつ A[i] > key    | c4 |   \sum_{j=2}^n t_j   |
      do A[i + 1] ← A[i]          | c5 |\sum_{j=2}^n {(t_j-1)}|
         i ← i - 1                | c6 |\sum_{j=2}^n {(t_j-1)}|
    A[i + 1] ← key                | c7 |         n-1          |

よって、INSERTION-SORTの実行時間はコストと回数の積和から次式を得る。
$T(n) = c_1 n + c_2(n-1) + c_3(n-1) + c_4\sum_{j=2}^n t_j + c_5\sum_{j=2}^n {(t_j-1)} + c_6 \sum_{j=2}^n {(t_j-1)} + c_7 (n-1)$
また、最良時と最悪時の計算量については $t_j$ の条件を検討することにより求めることができる。ちなみに挿入ソートにおいては、配列が整列されている時が最良で、逆順で並んでいる時が最悪である。

実験

次の3種類の配列についてベンチマークを取った(Ruby)。

ランダムな配列（値の範囲は配列長の10倍）
整列された配列を逆順にしたもの
整列された配列

以下のグラフを見ると逆順の配列が最も時間がかかっていることが分かる。

ベンチマークのコードを以下に示す。

require "benchmark"

MAX = 10000
STEP = 1000

rand = ->(i){a = Array.new(i).map{|j| rand(i * 10)}}
rseq = ->(i){(0..i).to_a.reverse}
seq  = ->(i){(0..i).to_a}

def benchmark_insertion
  puts Benchmark::CAPTION
  0.step(MAX, STEP){|i|
    a = yield.call(i)
    puts Benchmark.measure{
      insertion_sort(a)
    }
  }
end


benchmark_insertion{rand}
benchmark_insertion{rseq}
benchmark_insertion{seq}

表の数値におけるtotalの値を用いた。

結果

ランダムな値の入った配列

      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000000)
  0.047000   0.000000   0.047000 (  0.048000)
  0.171000   0.000000   0.171000 (  0.190000)
  0.421000   0.000000   0.421000 (  0.440000)
  0.718000   0.000000   0.718000 (  0.774000)
  1.232000   0.000000   1.232000 (  1.248000)
  1.732000   0.000000   1.732000 (  1.739000)
  2.449000   0.000000   2.449000 (  2.452000)
  3.135000   0.000000   3.135000 (  3.143000)
  3.963000   0.000000   3.963000 (  4.036000)
  4.851000   0.000000   4.851000 (  5.037000)

反転整列した配列

      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000000)
  0.078000   0.000000   0.078000 (  0.097000)
  0.375000   0.000000   0.375000 (  0.384000)
  0.873000   0.000000   0.873000 (  0.862000)
  1.560000   0.000000   1.560000 (  1.560000)
  2.418000   0.000000   2.418000 (  2.426000)
  3.401000   0.000000   3.401000 (  3.493000)
  4.743000   0.015000   4.758000 (  4.750000)
  6.193000   0.000000   6.193000 (  6.192000)
  7.753000   0.000000   7.753000 (  7.921000)
  9.672000   0.000000   9.672000 (  9.750000)

整列された配列

      user     system      total        real
  0.000000   0.000000   0.000000 (  0.000000)
  0.000000   0.000000   0.000000 (  0.000000)
  0.000000   0.000000   0.000000 (  0.001000)
  0.000000   0.000000   0.000000 (  0.001000)
  0.000000   0.000000   0.000000 (  0.001000)
  0.000000   0.000000   0.000000 (  0.001000)
  0.000000   0.000000   0.000000 (  0.002000)
  0.000000   0.000000   0.000000 (  0.002000)
  0.000000   0.000000   0.000000 (  0.002000)
  0.000000   0.000000   0.000000 (  0.002000)
  0.000000   0.000000   0.000000 (  0.003000)

ちなみに

グラフはmatplotlibで出力した。日本語出力は面倒なので英語のキャプションにしたけど言葉がおかしいかも。英語は苦手（´；ω；｀）

Soleil cou coupe