達人出版社でアルゴリズムを学ぼうという本を購入しました。
既に知っている内容から、何となくは知っていたけど理解があやふやだったというものが掲載されているので、頭の体操がてらには丁度いい印象です。
本書ではJavaで書かれていますが、Rubyで書きなおしてみます。
本文中に"Pythonとか、Rubyとかを使うべきなんだろうが、やつらはちょっと適当に書けすぎる"とありますが、気にしないことにします。
下記は、第3講で紹介されているソートアルゴリズムになります。(gist)
- バブルソート
- 選択ソート
- 挿入ソート
- マージソート
- クイックソート
- ヒープソート
実質Arrayへの拡張になっていますが、ちょっとはRubyらしく、ブロックを受け取ることことで昇順、降順をはじめ任意の並び替えに対応させています。
普段は至極当然ですが、Array#sortを使っています。
lib/sort.rb
module Sort
def compare_to? x, y, &block
return block ? block.call(x, y) : x < y
end
def bubblesort &block
ary = self.clone
(ary.size).downto(0) do |i|
(0...(ary.size - 1)).each do |j|
break if j > i
unless compare_to? ary[j], ary[j+1], &block
ary[j], ary[j+1] = ary[j+1], ary[j]
end
end
end
ary
end
def selectionsort &block
ary = self.clone
ary.each_index do |i|
((i+1)...(ary.size)).each do |j|
unless compare_to? ary[i], ary[j], &block
ary[i], ary[j] = ary[j], ary[i]
end
end
end
ary
end
def insertionsort &block
ary = self.clone
(1...ary.size).each do |i|
j = i
while (j > 0)
unless compare_to? ary[j-1], ary[j], &block
ary[j-1], ary[j] = ary[j], ary[j-1]
end
j -= 1
end
end
ary
end
def mergesort &block
mergesort_bang self, &block
end
def mergesort_bang ary, &block
return ary if ary.size <= 1
mid = ary.size / 2
left = mergesort_bang ary[0...mid], &block
right = mergesort_bang ary[mid..-1], &block
merge left, right, &block
end
def merge x, y, &block
work = []
loop do
if x.empty?
work << y
break
end
if y.empty?
work << x
break
end
compare_to?(x[0], y[0], &block) ? work << x.shift : work << y.shift
end
work.flatten
end
def quicksort &block
quicksort_bang self, &block
end
def quicksort_bang items, &block
pivot = items[0]
parts = items.partition { |i| compare_to? i, pivot, &block }
lower, upper = parts[0], parts[1]
if parts.all? { |i| i.size <= 1}
return lower.concat(upper).flatten
end
# split [x][y,z, ...] if "[][x,y,z, ...]"
lower = upper.shift(1) if lower.size == 0
upper = lower.shift(1) if upper.size == 0
p1 = quicksort_bang(lower, &block)
p2 = quicksort_bang(upper, &block)
p1.concat p2
end
def heapsort &block
heap = Heap.new &block
self.each { |i| heap.push i }
ary = []
until (heap.values.empty?)
ary << heap.pop
end
ary
end
end
class Heap
attr_reader :values
def initialize values=[], &block
@values = values
@block = Proc.new &block if block_given?
end
def compare_to? x, y
return @block ? @block.call(x, y) : x < y
end
def parent c
(c - 1) / 2
end
def left c
2 * c + 1
end
def right c
2 * c + 2
end
def push v
@values.push(v)
c = @values.rindex v
while (c > 0)
break if compare_to? @values[parent(c)], @values[c]
@values[parent(c)], @values[c] = @values[c], @values[parent(c)]
c = parent(c)
end
end
def pop
value = @values.shift
return value if @values.empty?
@values.unshift @values.pop
c = 0
while (@values[left(c)] || @values[right(c)])
child = !@values[right(c)] || compare_to?(@values[left(c)], @values[right(c)]) ? left(c) : right(c)
if compare_to? @values[child], @values[c]
@values[c], @values[child] = @values[child], values[c]
c = child
else
break
end
end
return value
end
end
spec/sort_spec.rb
require 'spec_helper'
shared_examples_for 'sort [](empty)' do
let(:ary) do
ary = []
ary.extend Sort
ary
end
it { should == [] }
end
shared_examples_for 'ascending sort [2, 6, 1, 0, 5, 4, 3]' do
let(:ary) do
ary = [2, 6, 1, 0, 5, 4, 3]
ary.extend Sort
ary
end
it { should == [0, 1, 2, 3, 4, 5, 6] }
end
shared_examples_for "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
let(:ary) do
ary = ['C', 'B', 'A', 'F', 'E', 'D']
ary.extend Sort
ary
end
it { should == ['F', 'E', 'D', 'C', 'B', 'A'] }
end
describe Sort do
context "#bubblesort" do
subject { ary.bubblesort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.bubblesort { |a, b| a > b} }
end
end
context "#selectionsort" do
subject { ary.selectionsort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.selectionsort { |a, b| a > b} }
end
end
context "#insertionsort" do
subject { ary.insertionsort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.insertionsort { |a, b| a > b} }
end
end
context "#mergesort" do
subject { ary.mergesort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.mergesort { |a, b| a > b} }
end
end
context "#quicksort" do
subject { ary.quicksort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.quicksort { |a, b| a > b} }
end
end
context "#heapsort" do
subject { ary.heapsort }
it_behaves_like 'sort [](empty)'
it_behaves_like 'ascending sort [2, 6, 1, 0, 5, 4, 3]'
it_behaves_like "sort ['C', 'B', 'A', 'F', 'E', 'D'] with block as desending" do
subject { ary.heapsort { |a, b| a > b} }
end
end
end
describe Heap do
context "#push" do
context "when push '4' to [5, 8]" do
subject do
heap = Heap.new([5,8])
heap.push 4
heap.values
end
it { should == [4, 8, 5]}
end
context "when push '3' to [4, 9, 7, 8]" do
subject do
heap = Heap.new([4, 9, 7, 8])
heap.push 3
heap.values
end
it { should == [3, 4, 7, 8, 9]}
end
end
context "#pop" do
context "when pop from [4, 9, 7, 8, 10]" do
let(:heap) { heap = Heap.new([4, 9, 7, 8, 10]) }
it "returns 4" do
heap.pop.should == 4
end
it "re-build heap as [7, 9, 10, 8]" do
heap.pop
heap.values.should == [7, 9, 10, 8]
end
end
context "when pop from [](empty)" do
let(:heap) { heap = Heap.new }
it "returns nil" do
heap.pop.should be_nil
end
it "no change heap as []" do
heap.pop
heap.values.should == []
end
end
end
end
spec/spec_helper.rb
require 'pry'
require 'pry-nav'
require 'sort'
