選択ソート

選択ソートとは

選択ソートは配列の最小値(最大値)を持つ要素を探して、それを配列の先頭要素と交換することで整列を行うアルゴリズムです。

Pseudocodeは以下のような感じ

配列の先頭要素を仮の最小値を持つ要素(A0)としておく

(A0)と(A0)以外の要素の値を比較して(A0)より小さい値を持つ要素(A1)が見付かれば(A1)と(A0)の値を交換する

2.を繰り返すことで(A0)には配列内での最小値がセットされる

次は(A0)を除いて(A1)と(A1)以外の要素、(A1)を除いて(A2)と(A2)以外の要素を比較/交換して整列が完了する

(引用元：選択ソート : アルゴリズム)

ロジック的にはできたかなと思いますが、最小を探すところがもっとうまくできるかなという印象です。

def selection_sort(arr)
    n = 0 
    (arr.length - 1).times do |i|
        min_i = arr.find_index(arr[n..arr.length - 1].min) #未ソート部分の最小値のインデックスを探しています。
        if arr[min_i] < arr[i]
          arr[min_i], arr[i] = arr[i], arr[min_i]
        end
        n += 1 
    end
    return arr
end

def selection_sort(arr)
    sorted = []
    while true
        return sorted if arr.size == 0
        sorted << arr.min
        arr.delete(arr.min)
    end
end

これは一番初めに書いた選択ソートですが、これはルール違反な気もします。

以下参考にしたコードです。

Rubyでソート・アルゴリズムを表現しよう!

Rubyで選択ソート。 - Qiita