挿入ソート(insertion sort)
先頭から整列していき、整列部後方から挿入値を順次比較して適切な位置に挿入する。挿入と言いつつ、動きは交換交換の荒らしなんだよなぁ。結果的には挿入したように見えるんだけど。ちなみに自分で書けなくて Wikipedia を参考にした orz
def insertion_sort(list) dup = list.dup 1.upto(dup.length - 1) {|i| tmp = dup[i] j = 0 i.downto(0) {|j| break if dup[j - 1] <= tmp dup[j] = dup[j - 1] } dup[j] = tmp } dup end