ソート

達人出版社でアルゴリズムを学ぼうという本を購入しました。
既に知っている内容から、何となくは知っていたけど理解があやふやだったというものが掲載されているので、頭の体操がてらには丁度いい印象です。
本書では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'