Commit 800887e

@@ -0,0 +1,20 @@
+class QuickUnion
+  def initialize(size)
+    @items = Array.new(size) { |n| n }
+  end
+
+  def union(x, y)
+    @items[x] = root_of(y)
+  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

@@ -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

@@ -1,6 +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'