【アルゴリズムの勉強】Rubyで選択ソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで選択ソートを実装する。

選択ソートとは

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。
このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。

選択ソート - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count

def selection_sort(arr, number_of_elements)
  (number_of_elements - 1).times{|i|
    min = i
    for j in (i + 1)..(number_of_elements - 1)
      if arr[j] < arr[min]
        min = j;
      end
    end
    arr[i], arr[min] = arr[min], arr[i]
  }
  return arr
end

sorted_arr = selection_sort(arr, number_of_elements)
p sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献