概要
挿入ソート
内容
整列してある配列に追加要素を適切な場所に挿入すること。
平均計算時間・最悪計算時間がともにO(n2)。
ソート仕様
・左端から順にN番目の要素をN-1番目までの要素と比較して、自分より小さい値と大きい値の間に挿入する。
コード
insert_sort.rb
# encoding: utf-8 class Array def insert_sort inject([]) do |total, value| index = find_index{|other|value <= other} || total.size total.insert(index, value) end end end
テストコード
insert_sort_spec.rb
# encoding: utf-8 require_relative "../insert_sort" describe Array do cases = [ { input_ary: [5,4,3,2,1], expected: [1,2,3,4,5] }, { input_ary: [1,2,3,4,5], expected: [1,2,3,4,5] }, { input_ary: [1,4,3,2,5], expected: [1,2,3,4,5] }, { input_ary: [2,4,3,5,1], expected: [1,2,3,4,5] }, { input_ary: [3,4,5,2,1], expected: [1,2,3,4,5] } ] cases.each do |c| it "#insert_sort" do actual = c[:input_ary].insert_sort expect(actual).to eq(c[:expected]) end end end