アルゴリズム | 選択ソート

概要

選択ソート

内容

最小値を探し、先頭から順に並べていくソート。
O(n2)と低速だが実装が容易。

コード

selection_sort.rb

class Array
  def selection_sort
    max = self.size - 1
    (0..max).each do |i|
      min = i
      ((i + 1)..max).each do |j|
        min = j if self[j] < self[min]
      end
      tmp = self[i]
      self[i] = self[min]
      self[min] = tmp
    end
    return self
  end
end

テストコード

selection_sort_spec.rb

# encoding: utf-8
require_relative "../selection_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 "#selection_sort" do
      actual = c[:input_ary].selection_sort
      expect(actual).to eq(c[:expected])
    end
  end
end