# State of the QuickUnion

In my last look at the UnionFind algorithm I made a quick-find implementation — finding if two elements were connected was fast but connecting two elements was slow. The union operation is a good candidate for optimization.

# Quick Union

One way to optimize the union operation is to reduce the number of array accesses required.

In QuickFind, the sets are arranged in a flat array of elements which all share the same value: they are all wearing the same t-shirt. When we connect elements from different sets, we must make sure that every element in the first set changes its t-shirt to match the elements in the other set. This is a time-consuming process, and uses a lot of t-shirts.

What if only one element had to change its t-shirt? If the set had a single element in charge – a root – then joining elements from different sets would require identifying the t-shirt of the one in charge, and then changing to that element’s t-shirt.

Using an array instead of t-shirts to keep track of the values, we can walk through what this implementation would look like:

 Index Value union(4,9) union(2,4) union(4,7) find(2,7) 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 | Each element begins as the root of its own set 1 2 3 9 5 6 7 8 9 0 | root(9) = 9, root(4) = 4, change array = 9 1 9 3 9 5 6 7 8 9 0 | root(4) = 9, root(2) = 2, change array = 9 1 9 3 9 5 6 7 8 7 0 | root(7) = 7, root(4) = 9, change array = 7 1 9 3 9 5 6 7 8 7 0 | root(7) = 7, root(2) = 7. The two are connected

## QuickUnion

Again following the basic API:

``````public class UF
---------------
public UF(int N)
public int find(int p, int q)
public void union(int p, int q)``````

I adapted the QuickUnion in ruby:

``````class QuickUnion
def initialize(size)
@find_array = Array.new(size){ |index| index }
end

# check if p and q have the same root
def find(p, q)
verify(p, q)
root(p) == root(q)
end

# set id of p's root to the id of q's root
def union(p, q)
verify(p, q)
@find_array[root(p)] = root(q)
end

private
def root(index)
# get root until root(index) == index
if @find_array[index] == index
return index
else
root(@find_array[index])
end
end

def verify(p, q)
raise NotAnElement if @find_array[p].nil?
raise NotAnElement if @find_array[q].nil?
end
end

class NotAnElement < Exception
end``````

This implementation is a QuickUnion because in an array of 1,000,000 entries, connecting element p to element q is easy: you only have to find the root of p, and then change q to match (one root() and one array access). Finding if p and q are connected takes a little bit longer, because you have to perform two root operations: one for p and one for q, but it is still faster than accessing every element in the array.

## Benchmark

``````\$ ruby lib/benchmark.rb
=> Array Size: 100
user     system      total        real
0.000000   0.000000   0.000000 (  0.001865)
0.000000   0.000000   0.000000 (  0.000377)
\$ ruby lib/benchmark.rb
=> Array Size: 1000
user     system      total        real
0.120000   0.010000   0.130000 (  0.124929)
0.010000   0.000000   0.010000 (  0.008825)
\$ ruby lib/benchmark.rb
=> Array Size: 10000
user     system      total        real
10.120000   0.030000  10.150000 ( 10.146124)
0.520000   0.000000   0.520000 (  0.520377)``````

Comparing QuickFind (top line) with QuickUnion(bottom line), we can actually measure how well this small optimization of the union operation has increased performance with larger datasets.

Awesome.