新ソートアルゴリズム「配列挿入ソート」だ!
以前にスリープソートというソートアルゴリズムが発見されたよね。
常識を覆すソートアルゴリズム！その名も”sleep sort”！ - Islands in the byte stream
で、僕はこれに対抗してランニングソートっていうアルゴリズムを見つけたんだよ。まあ失敗したんだけど..
sleep sortに対抗してrunning sortだ！（Ruby版｜失敗に終わる編）
で、今回また新たなソートアルゴリズムを発見したから、みんなに紹介するよ。
その名も「配列挿入ソート」!
これはいわば挿入ソートの簡易版だよ。まずはRubyで挿入ソートを書いてみるよ。だいたいこんな感じになるよ。
class Array
def insert_sort
inject([]) { |mem, var| mem.insert_with_order(var) }
end
def insert_with_order(item)
pos = find_index { |n| item <= n } || length
insert(pos, item)
end
end
require "mathn"
l = Prime.take(10).sort_by { rand } # => [7, 2, 3, 11, 17, 19, 29, 5, 23, 13]
l.insert_sort # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]これに対して配列挿入ソートはこうだよ。
class Array
def array_insert_sort
inject([]) { |mem, var| mem[var] = var; mem }.compact
end
end
require "mathn"
l = Prime.take(10).sort_by { rand } # => [7, 2, 3, 11, 17, 19, 29, 5, 23, 13]
l.array_insert_sort # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]なんてことはない、ただ要素を配列のインデックスに対応付けて、配置し直しただけだよ。この前投稿したRubyで連続数字をハイフンでつなぐよのときに気が付いたんだ。
で、ちょっと改良すれば文字のソートにも対応できるんだよ。
class Array
def array_insert_sort
inject([]) { |mem, var| mem[var.ord] = var; mem }.compact
end
end
require "mathn"
l = Prime.take(10).sort_by { rand } # => [13, 3, 29, 5, 17, 2, 11, 7, 19, 23]
l.array_insert_sort # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
c = "The quick brown fox jumps over the lazy dog".scan(/\w/) # => ["T", "h", "e", "q", "u", "i", "c", "k", "b", "r", "o", "w", "n", "f", "o", "x", "j", "u", "m", "p", "s", "o", "v", "e", "r", "t", "h", "e", "l", "a", "z", "y", "d", "o", "g"]
c.array_insert_sort # => ["T", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]まあ文字列と重複要素には使えないけどね..
念のため実行速度を見てみるね。比較対象はRuby標準のsort、挿入ソート、クイックソートだよ。クイックソートの実装は次の通りだよ。
class Array
def quick_sort
return self if length <= 1
base = pop
smaller, bigger = partition { |e| e < base }
push base
smaller.quick_sort + [base] + bigger.quick_sort
end
endさあベンチマークを取るよ。
require "benchmark"
Benchmark.bmbm do |bm|
l = Prime.take(10000).sort_by { rand }
bm.report { l.sort }
bm.report { l.quick_sort }
bm.report { l.insert_sort }
bm.report { l.array_insert_sort }
end
# >> Rehearsal ------------------------------------
# >> 0.000000 0.000000 0.000000 ( 0.002726)
# >> 0.050000 0.000000 0.050000 ( 0.049841)
# >> 3.560000 0.000000 3.560000 ( 3.565532)
# >> 0.010000 0.010000 0.020000 ( 0.007513)
# >> --------------------------- total: 3.630000sec
# >>
# >> user system total real
# >> 0.000000 0.000000 0.000000 ( 0.002579)
# >> 0.050000 0.000000 0.050000 ( 0.049816)
# >> 3.550000 0.000000 3.550000 ( 3.561074)
# >> 0.010000 0.000000 0.010000 ( 0.006725)こりゃ素晴らしい!
(追記:2012-1-10) id:m11m さんのコメントによりこのソートはバケットソートと呼ばれる既知のソートアルゴリズムであることがわかりました ^ ^; 追記によりお詫び申し上げます
(追記:2012-1-12) 記事に対するアクセスが異常なので調べてみると、dankogai氏のネタにされていたという名誉を受けていたことが判明しました^ ^; 光栄です 404 Blog Not Found:algorithm - bucket sort - 比較しなければソートは相当速い
(comment)
>このアルゴリズムをバケットソート，あるいはビンソートと呼びます．
»m11mさん
コメントありがとうございます。既知のアルゴリズムだったとは無知を晒してしまいました。^ ^;情報ありがたいです。
blog comments powered by Disqus
