練習:挿入ソート
調子に乗って、今度は挿入ソートを。クイックソートで範囲が狭まってから使うと効果的。Javaで試したけど、ほぼ同じか気持ち速かったようでした。
クイックソートと同様に、モジュールとして定義。さらに、フラグを立てると実行状況が出力されるようにしてみました。
module Sort module InsertionSort def sort (f = 0, t = self.size - 1) self.clone.sort!(f, t) end def sort! (f = 0, t = self.size - 1) (f + 1..t).each do |i| x = self[i] $debug and self[i] = "--" $debug and printf "S %02d %s %s\n", i, x, self.inspect while i > f break if self[i - 1] <= x self[i], self[i - 1] = self[i - 1], self[i] i -= 1 $debug and printf " %02d %s %s\n", i, x, self.inspect end self[i] = x $debug and x = '"--"' $debug and printf "E %02d %s %s\n", i, x, self.inspect end self end end end $debug = true o = Array.new(8) do |i| rand(9000) + 1000 end x = o.clone.extend Sort::InsertionSort puts o.sort == x.sort
実行状況。"S"の行は取り出した直後の状態。"E"は並び替えた後で取り出したのを戻したところ。それ以外は、入れ替え中の状態。
S 01 4154 [8118, "--", 5797, 3376, 2323, 5466, 3113, 3086] 00 4154 ["--", 8118, 5797, 3376, 2323, 5466, 3113, 3086] E 00 "--" [4154, 8118, 5797, 3376, 2323, 5466, 3113, 3086] S 02 5797 [4154, 8118, "--", 3376, 2323, 5466, 3113, 3086] 01 5797 [4154, "--", 8118, 3376, 2323, 5466, 3113, 3086] E 01 "--" [4154, 5797, 8118, 3376, 2323, 5466, 3113, 3086] S 03 3376 [4154, 5797, 8118, "--", 2323, 5466, 3113, 3086] 02 3376 [4154, 5797, "--", 8118, 2323, 5466, 3113, 3086] 01 3376 [4154, "--", 5797, 8118, 2323, 5466, 3113, 3086] 00 3376 ["--", 4154, 5797, 8118, 2323, 5466, 3113, 3086] E 00 "--" [3376, 4154, 5797, 8118, 2323, 5466, 3113, 3086] S 04 2323 [3376, 4154, 5797, 8118, "--", 5466, 3113, 3086] 03 2323 [3376, 4154, 5797, "--", 8118, 5466, 3113, 3086] 02 2323 [3376, 4154, "--", 5797, 8118, 5466, 3113, 3086] 01 2323 [3376, "--", 4154, 5797, 8118, 5466, 3113, 3086] 00 2323 ["--", 3376, 4154, 5797, 8118, 5466, 3113, 3086] E 00 "--" [2323, 3376, 4154, 5797, 8118, 5466, 3113, 3086] S 05 5466 [2323, 3376, 4154, 5797, 8118, "--", 3113, 3086] 04 5466 [2323, 3376, 4154, 5797, "--", 8118, 3113, 3086] 03 5466 [2323, 3376, 4154, "--", 5797, 8118, 3113, 3086] E 03 "--" [2323, 3376, 4154, 5466, 5797, 8118, 3113, 3086] S 06 3113 [2323, 3376, 4154, 5466, 5797, 8118, "--", 3086] 05 3113 [2323, 3376, 4154, 5466, 5797, "--", 8118, 3086] 04 3113 [2323, 3376, 4154, 5466, "--", 5797, 8118, 3086] 03 3113 [2323, 3376, 4154, "--", 5466, 5797, 8118, 3086] 02 3113 [2323, 3376, "--", 4154, 5466, 5797, 8118, 3086] 01 3113 [2323, "--", 3376, 4154, 5466, 5797, 8118, 3086] E 01 "--" [2323, 3113, 3376, 4154, 5466, 5797, 8118, 3086] S 07 3086 [2323, 3113, 3376, 4154, 5466, 5797, 8118, "--"] 06 3086 [2323, 3113, 3376, 4154, 5466, 5797, "--", 8118] 05 3086 [2323, 3113, 3376, 4154, 5466, "--", 5797, 8118] 04 3086 [2323, 3113, 3376, 4154, "--", 5466, 5797, 8118] 03 3086 [2323, 3113, 3376, "--", 4154, 5466, 5797, 8118] 02 3086 [2323, 3113, "--", 3376, 4154, 5466, 5797, 8118] 01 3086 [2323, "--", 3113, 3376, 4154, 5466, 5797, 8118] E 01 "--" [2323, 3086, 3113, 3376, 4154, 5466, 5797, 8118] true
これちょっと気に入った。