Rubyでソートを考える④シェルソート
体調がいまいちなのは昨日の遊び疲れかな。
いや、突然1日6時間も引き継ぎミーティング入れられたからかもしれない。
ハードすぎるよ、先週までの穏やかな毎日を返して!!!
今日は「シェルソート」!!!
シェルソートとは(処理方法)
適当な間隔を決め、この間隔だけ離れた要素同士だけで挿入ソート。
その後、間隔を少し狭めて、やはりその間隔だけ離れた要素同士だけで挿入ソート。
これを繰り返していくと、最終的には間隔 = 1となり、この時点で結構「整列済み」な状態になってるはず。
間隔 = 1で挿入ソートを行うことは、普通に挿入ソートを行うということ。
ただし、挿入ソートは整列済みになっている部分が多いほど処理速度が向上する特性があるので、最後の挿入ソートはかなり高速に終わるはず!
これ面白い。ちゃんとシェルソートになってる!!
Shell-sort with Hungarian (Székely) folk dance - YouTube
# coding: windows-31j #------------------------------ #シェルソートをしてみる #2015/08/24 #------------------------------ puts "英単語をabc順に並び替えるよ!!" puts "英単語を何個でも入力してください。" puts "最後はEnterだけの空行にしてください" #配列 words = [] while word = gets.chomp break if word.empty? words << word end repeat = words.length gap = repeat / 2 while gap > 0 0.upto(gap - 1) do |num1| num2 = num1 + gap while num2 < repeat num3 = num2 - gap while num3 >= num1 if words[num3] > words[num3 + gap] words[num3], words[num3 + gap] = words[num3 + gap], words[num3] else break end num3 = num3 - gap end num2 = num2 + gap end end gap = gap / 2 end puts "並び替えが完了しました!" puts words