Rubyで挿入ソート

今日もアルゴリズムの勉強。

概要

リストの整列済みの部分に対して、新たな要素を比較し適切な位置に挿入して整列を行う。

実装方法

• 先頭の要素を整列済みとして、次の要素を整列対象とする。
• 整列対象の要素と整列済み要素を比較して、適切な位置に挿入する。
• 要素がなくなるまで繰り返す。

サンプルプログラム

def InsertionSort(array)
  len = array.length

  (1..(len-1)).each do |i| 
    tmp = array[i]
    j = i - 1 

    puts "----- #{i}回目 -----"

    while j >= 0
      if tmp < array[j]
        array[j], array[j+1] = array[j+1], array[j]
      end 
      j -= 1
      p array
    end 
  end 
  return array
end

ary = [*1..10].shuffle
puts "#{ary} <-- 初期値\n\n"
InsertionSort(ary)

実行結果

[9, 10, 1, 8, 6, 5, 4, 2, 7, 3] <-- 初期値

----- 1回目 -----
[9, 10, 1, 8, 6, 5, 4, 2, 7, 3]
----- 2回目 -----
[9, 1, 10, 8, 6, 5, 4, 2, 7, 3]
[1, 9, 10, 8, 6, 5, 4, 2, 7, 3]
----- 3回目 -----
[1, 9, 8, 10, 6, 5, 4, 2, 7, 3]
[1, 8, 9, 10, 6, 5, 4, 2, 7, 3]
[1, 8, 9, 10, 6, 5, 4, 2, 7, 3]
----- 4回目 -----
[1, 8, 9, 6, 10, 5, 4, 2, 7, 3]
[1, 8, 6, 9, 10, 5, 4, 2, 7, 3]
[1, 6, 8, 9, 10, 5, 4, 2, 7, 3]
[1, 6, 8, 9, 10, 5, 4, 2, 7, 3]
----- 5回目 -----
[1, 6, 8, 9, 5, 10, 4, 2, 7, 3]
[1, 6, 8, 5, 9, 10, 4, 2, 7, 3]
[1, 6, 5, 8, 9, 10, 4, 2, 7, 3]
[1, 5, 6, 8, 9, 10, 4, 2, 7, 3]
[1, 5, 6, 8, 9, 10, 4, 2, 7, 3]
----- 6回目 -----
[1, 5, 6, 8, 9, 4, 10, 2, 7, 3]
[1, 5, 6, 8, 4, 9, 10, 2, 7, 3]
[1, 5, 6, 4, 8, 9, 10, 2, 7, 3]
[1, 5, 4, 6, 8, 9, 10, 2, 7, 3]
[1, 4, 5, 6, 8, 9, 10, 2, 7, 3]
[1, 4, 5, 6, 8, 9, 10, 2, 7, 3]
----- 7回目 -----
[1, 4, 5, 6, 8, 9, 2, 10, 7, 3]
[1, 4, 5, 6, 8, 2, 9, 10, 7, 3]
[1, 4, 5, 6, 2, 8, 9, 10, 7, 3]
[1, 4, 5, 2, 6, 8, 9, 10, 7, 3]
[1, 4, 2, 5, 6, 8, 9, 10, 7, 3]
[1, 2, 4, 5, 6, 8, 9, 10, 7, 3]
[1, 2, 4, 5, 6, 8, 9, 10, 7, 3]
----- 8回目 -----
[1, 2, 4, 5, 6, 8, 9, 7, 10, 3]
[1, 2, 4, 5, 6, 8, 7, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 3]
----- 9回目 -----
[1, 2, 4, 5, 6, 7, 8, 9, 3, 10]
[1, 2, 4, 5, 6, 7, 8, 3, 9, 10]
[1, 2, 4, 5, 6, 7, 3, 8, 9, 10]
[1, 2, 4, 5, 6, 3, 7, 8, 9, 10]
[1, 2, 4, 5, 3, 6, 7, 8, 9, 10]
[1, 2, 4, 3, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

参考

挿入ソート [Insertion Sort]