IT Soldier Sakuri !!

Oracle使い。いつのまにかIT戦士になってしまったさくりの可哀想な奮闘記。

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