Skip to content

Instantly share code, notes, and snippets.

@taylorlapeyre
Forked from yknd/Guardfile
Created December 12, 2012 01:07
Show Gist options
  • Save taylorlapeyre/4263963 to your computer and use it in GitHub Desktop.
Save taylorlapeyre/4263963 to your computer and use it in GitHub Desktop.
These are implements of sort algorithm for Ruby.
- bubble sort
- selection sort
- insertion sort
- merge sort
- quick sort
- heap sort
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
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
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
require 'pry'
require 'pry-nav'
require 'sort'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment