挿入ソートのベンチマーク（Ruby）

Rubyっぽく書いたのと教科書の擬似コードをそのまま書いたものとの比較。

require 'benchmark'

class Array
  def insertion_sort1
    ar = self
    (size - 1).times do |i|
      key = ar[i + 1]
      j = ar.index {|x| x >= key}
      next if j >= i + 1
      ar = ar[0...j] + [key] + ar[j..i] + ar[i + 2..-1]
    end
    ar
  end
  
  def insertion_sort2
    (size - 1).times do |j|
      key = at(j + 1)
      i = j
      while i >= 0 and at(i) > key
        self[i + 1] = at(i)
        i -= 1
      end
      self[i + 1] = key
    end
    self
  end
end

ar = [*0..10000].shuffle
Benchmark.bm do |x|
  x.report {ar.dup.insertion_sort1}
  x.report {ar.dup.insertion_sort2}
end

1 の方は非破壊的で安定でない、2 の方は破壊的で安定。
結果。

       user     system      total        real
   1.430000   0.070000   1.500000 (  1.498388)
   2.330000   0.000000   2.330000 (  2.330626)

Rubyっぽく書いた方が約1.5倍速かった。

もうひとつ思いついた。破壊的で安定でない。

class Array
  def insertion_sort3
    (size - 1).times do |i|
      key = at(i + 1)
      j = index{|x| x >= key}
      if j != i + 1
        delete_at(i + 1)
        insert(j, key)
      end
    end
    self
  end
end

結果。

       user     system      total        real
   1.370000   0.080000   1.450000 (  1.451847)
   2.390000   0.000000   2.390000 (  2.386278)
   1.250000   0.000000   1.250000 (  1.250350)

これがいちばん速かった。意外。
　

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)