sample sort

readme

These are implements of sort algorithm for Ruby.

- bubble sort
- selection sort
- insertion sort
- merge sort
- quick sort
- heap sort

Guardfile

guard 'rspec', :version => 2, :cli => "-c -fs" do
  watch(%r{^spec/.+_spec\.rb$})
  watch(%r{^lib/(.+)\.rb$})     { |m| "spec/#{m[1]}_spec.rb" }
  watch('spec/spec_helper.rb')  { "spec" }
  watch(%r{^views/(.+)\.(slim|scss)$})
end

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

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_helper.rb

require 'pry'
require 'pry-nav'
require 'sort'