Merge branch 'master' of github.com:mokhan/algorithms

6 files changed, 157 insertions, 4 deletions

diff --git a/lib/quick_find.rb b/lib/quick_find.rb
new file mode 100644
index 0000000..419ed8b
--- /dev/null
+++ b/lib/quick_find.rb
@@ -0,0 +1,23 @@
+class QuickFind
+  def initialize(size)
+    @items = []
+    size.times.each do |n|
+      @items[n] = n
+    end
+  end
+
+  def connected?(x, y)
+    @items[x] == @items[y]
+  end
+
+  def union(x, y)
+    x_value = @items[x]
+    y_value = @items[y]
+
+    @items.size.times do |n|
+      if @items[n] == x_value
+        @items[n] = y_value
+      end
+    end
+  end
+end
diff --git a/lib/quick_union.rb b/lib/quick_union.rb
new file mode 100644
index 0000000..f8a966b
--- /dev/null
+++ b/lib/quick_union.rb
@@ -0,0 +1,31 @@
+class QuickUnion
+  def initialize(size)
+    @items = Array.new(size) { |n| n }
+    @size = Array.new(size, 0)
+  end
+
+  def union(x, y)
+    i = root_of(x)
+    j = root_of(y)
+    return if (i == j)
+
+    if @size[i] < @size[j]
+      @items[i] = j
+      @size[j] = @size[j] + @size[i]
+    else
+      @items[j] = i
+      @size[i] = @size[i] + @size[j]
+    end
+  end
+
+  def connected?(x, y)
+    root_of(x) == root_of(y)
+  end
+
+  private
+
+  def root_of(x)
+    x = @items[x] until @items[x] == x
+    x
+  end
+end
diff --git a/spec/quick_find_spec.rb b/spec/quick_find_spec.rb
new file mode 100644
index 0000000..88929e3
--- /dev/null
+++ b/spec/quick_find_spec.rb
@@ -0,0 +1,60 @@
+require "spec_helper"
+
+describe QuickFind do
+  subject { QuickFind.new(10) }
+
+  it "is not connected by default" do
+    10.times do |n|
+      expect(subject.connected?(n, n+1)).to be_false
+    end
+  end
+
+  it "is connected" do
+    subject.union(0, 1)
+    expect(subject.connected?(0, 1)).to be_true
+  end
+
+  it "unions and connects properly" do
+    subject.union(4, 3)
+    expect(subject.connected?(4, 3)).to be_true
+    expect(subject.connected?(3, 4)).to be_true
+
+    subject.union(3, 8)
+    expect(subject.connected?(3, 8)).to be_true
+
+    subject.union(6, 5)
+    expect(subject.connected?(6, 5)).to be_true
+
+    subject.union(9, 4)
+    expect(subject.connected?(9, 4)).to be_true
+
+    subject.union(2, 1)
+    expect(subject.connected?(2, 1)).to be_true
+
+    subject.union(8, 9)
+    expect(subject.connected?(8, 9)).to be_true
+
+    expect(subject.connected?(5, 0)).to be_false
+    subject.union(5, 0)
+    expect(subject.connected?(5, 0)).to be_true
+    expect(subject.connected?(6, 0)).to be_true
+    expect(subject.connected?(5, 6)).to be_true
+
+    subject.union(7, 2)
+    subject.union(6, 1)
+
+    tuples = [
+      [0, 5],
+      [5, 6],
+      [6, 1],
+      [1, 2],
+      [2, 7],
+      [8, 3],
+      [3, 4],
+      [4, 9],
+    ]
+    tuples.each do |tuple|
+      expect(subject.connected?(tuple.first, tuple.last)).to be_true
+    end
+  end
+end
diff --git a/spec/quick_union_spec.rb b/spec/quick_union_spec.rb
new file mode 100644
index 0000000..362d2f2
--- /dev/null
+++ b/spec/quick_union_spec.rb
@@ -0,0 +1,33 @@
+require "spec_helper"
+
+describe QuickUnion do
+  subject { QuickUnion.new(10) }
+
+  it "is not connected" do
+    expect(subject.connected?(0, 1)).to be_false
+  end
+
+  it "is connected" do
+    subject.union(4, 3)
+    subject.connected?(4, 3).should be_true
+    subject.union(3, 8)
+    subject.connected?(3, 8).should be_true
+    subject.union(6, 5)
+    subject.connected?(6, 5).should be_true
+
+    subject.union(9, 4)
+    subject.connected?(9, 4).should be_true
+
+    subject.union(2, 1)
+    subject.connected?(8, 9).should be_true
+    subject.connected?(5, 4).should be_false
+    subject.union(5, 0)
+    subject.connected?(5, 0).should be_true
+    subject.union(7, 2)
+    subject.connected?(7, 2).should be_true
+    subject.union(6, 1)
+    subject.connected?(6, 1).should be_true
+    subject.union(7, 3)
+    subject.connected?(7, 3).should be_true
+  end
+end
diff --git a/spec/sorting/efficiency_spec.rb b/spec/sorting/efficiency_spec.rb
index 46bf5de..86505fd 100644
--- a/spec/sorting/efficiency_spec.rb
+++ b/spec/sorting/efficiency_spec.rb
@@ -1,6 +1,10 @@
 require "spec_helper"
 
 describe "Algorithm efficiency" do
+  let(:bubble_sort) { BubbleSort.new }
+  let(:insertion_sort) { InsertionSort.new }
+  let(:merge_sort) { MergeSort.new }
+  let(:quick_sort) { QuickSort.new }
 
   it "should sort an array of 100 numbers" do
     run(100)
@@ -21,10 +25,10 @@ describe "Algorithm efficiency" do
   def run(n)
     numbers = Array.new(n) { rand(n) }
     Benchmark.bmbm do |x|
-      x.report("#{n}-bubble") { BubbleSort.new.sort(numbers) }
-      x.report("#{n}-insertion") { InsertionSort.new.sort(numbers) }
-      x.report("#{n}-merge") { MergeSort.new.sort(numbers) }
-      x.report("#{n}-quick") { QuickSort.new.sort(numbers) }
+      x.report("#{n}-bubble") { bubble_sort.sort(numbers) }
+      x.report("#{n}-insertion") { insertion_sort.sort(numbers) }
+      x.report("#{n}-merge") { merge_sort.sort(numbers) }
+      x.report("#{n}-quick") { quick_sort.sort(numbers) }
       x.report("#{n}-ruby") { numbers.sort }
     end
   end
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 6cfb317..60746c2 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -1,5 +1,7 @@
 require 'benchmark'
 require_relative '../lib/in_order_traversal'
+require_relative '../lib/quick_find'
+require_relative '../lib/quick_union'
 
 require_relative '../lib/sorting/bubble_sort'
 require_relative '../lib/sorting/insertion_sort'