情報自炊

情報を血肉にしたい

挿入ソート

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

アルゴリズムイントロダクション 第3版 総合版:世界標準MIT教科書

アルゴリズムに強くなってAtCoderのレートを上げたいので基礎から勉強中。

本書には擬似コードが載っているが、せっかくなのでrubyで実装。

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

(1..(arr.length-1)).each do |j|
  key = arr[j]
  puts "j=#{j}, key=#{key}"
  # keyをソート済みの列に挿入
  i = j - 1
  while i >= 0 && arr[i] > key do
    puts "i=#{i}, arr[#{i + 1}]=#{arr[i + 1]}, arr[#{i}]=#{arr[i]}"
    arr[i + 1] = arr[i]
    i -= 1
  end
  arr[i + 1] = key
  puts "#{arr}"
  puts "------"
end

puts "after: #{arr}"

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

before: [3, 2, 1, 4, 5]
j=1, key=2
i=0, arr[1]=2, arr[0]=3
[2, 3, 1, 4, 5]
------
j=2, key=1
i=1, arr[2]=1, arr[1]=3
i=0, arr[1]=3, arr[0]=2
[1, 2, 3, 4, 5]
------
j=3, key=4
[1, 2, 3, 4, 5]
------
j=4, key=5
[1, 2, 3, 4, 5]
------
after: [1, 2, 3, 4, 5]