情報自炊

情報を血肉にしたい

選択ソート

最小のものを探して交換していくソート。実行時間はO(n^2)。「xxソート」という言葉と、その言葉が意味するアルゴリズムが紐付かないことがあるのでしっかり覚えるようにする。

# 選択ソート
arr = gets.chomp.split(" ").map(&:to_i)
puts "before: #{arr}"

(0..(arr.length-2)).each do |i|
  min = arr[i]
  min_j = i
  # 最小を見つける
  ((i+1)..(arr.length-1)).each do |j|
    if arr[j] < min then
      min = arr[j]
      min_j = j
    end
  end
  # arr[i]とarr[min_j]を交換
  tmp = arr[i]
  arr[i] = min
  arr[min_j] = tmp
  puts "#{i}: #{arr}"
end

puts "after: #{arr}"

実行例
標準入力:3 5 4 2 1

before: [3, 5, 4, 2, 1]
0: [1, 5, 4, 2, 3]
1: [1, 2, 4, 5, 3]
2: [1, 2, 3, 5, 4]
3: [1, 2, 3, 4, 5]
after: [1, 2, 3, 4, 5]