Rubyでソートを考える②挿入ソート

今日はまたすっごい暑い…
そんな中、午後からまつげエクステして、お買い物に行ってきた！
前に見て可愛いなって思ってたワンピースをやっぱり購入。
ウッキウキしながら、ベローチェでカフェプログラミングなう□＿ヾ(・_・ )ｶﾀｶﾀ

Rubyでソートを考える①バブルソート - IT Soldier Sakuri !!に引き続き、
ソートの勉強をしておるのです。

今日は「挿入ソート」でいこう！

挿入ソートとは(処理方法)
ソート(整列)済みの部分に対して次の要素を適切な位置に挿入するソート方法。
1番目と2番目の要素を比較し、順番が逆であれば入れ換える。
これで2番目までは整列していることになる。
2回目は、3番目の要素が2番目までの要素より小さい場合、正しい順に並ぶように挿入する。
これで3番目までは整列していることになる。
これを繰り返すことで、ソートが完成。

挿入ソートは整列されている部分が多いほど計算量が減るから処理速度が上がるみたい。
逆に、整列されているものを逆順(昇順→降順にする等)ときは全部並び替えるから遅くなる。

では、挿入ソートを書いてみよう。

# coding: windows-31j
#------------------------------
#挿入ソートをしてみる
#2015/08/22
#------------------------------

puts "英単語をabc順に並び替えるよ！！"
puts "英単語を何個でも入力してください。"
puts "最後はEnterだけの空行にしてください"

#配列
words = []

while word = gets.chomp
    break if word.empty?
    words << word
end

repeat = words.length

1.upto(repeat-1) do |num1|
    (num1-1).downto(0) do |num2|
        if words[num2] > words[num2+1]
            words[num2],words[num2+1] = words[num2+1],words[num2]
        else
            break
        end
    end
end

puts "並び替えが完了しました！"
puts words

色々なソートプログラムを作成したら、速度比較とかやってみたら面白いかな？