Rubyで選択ソート

引き続きアルゴリズムの勉強。

概要

選択ソートは配列の最小値（または最大値）を探索して、それを配列の先頭と入れ替えて整列を行うアルゴリズム。
バブルソートと異なり、配列の最小値のキーを保持して実装を行う。

サンプルプログラム

def selection_sort(array)
  len = array.length

  (0...len).each do |i| 
    # 先頭要素を最小値として定義
    min = array[i]
    min_key = i 

    ((i+1)...len).each do |j| 
      if min > array[j]
        min = array[j]
        min_key = j 
      end 
    end 
    temp = array[i]
    array[i] = min 
    array[min_key] = temp
  end 

  return array
end

ary = [*1..10].shuffle
p ary   # => [4, 9, 6, 1, 2, 5, 3, 10, 8, 7]

p selection_sort(ary)   # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

参考

Rubyで各種ソートアルゴリズム

選択ソート