argius note

プログラミング関連

練習:挿入ソート

調子に乗って、今度は挿入ソートを。クイックソートで範囲が狭まってから使うと効果的。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

これちょっと気に入った。