Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

アルゴリズム | 挿入ソート

概要

挿入ソート

内容

整列してある配列に追加要素を適切な場所に挿入すること。
平均計算時間・最悪計算時間がともに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