概要
選択ソート
内容
最小値を探し、先頭から順に並べていくソート。
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