挿入ソート

insertion_sort.rb

class Array
  def i_sort
    a = dup
    for j in 1...(a.size)
      key = a[j]
      i = j - 1
      while i >= 0 and a[i] > key
	a[i + 1] = a[i]
	i -= 1
      end
      a[i + 1] = key
    end
    a
  end
end

p [6, 0, 5, 2, 1].i_sort    #=>[0, 1, 2, 5, 6]

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

p.14
　
　
※参考