README

Quick Union Algorithm (from Sedgewick) Solved in C# using TDD

In "Algorithms in Java", by Robert Sedgewick, available on Amazon.com here: http://www.amazon.com/Bundle-Algorithms-Java-Third-Parts/dp/0201775786/

Chapter 1 explores a connectivity algorithm in increasingly complex iterations.

The goal of the connectivity process is as follows:

1. be able to add pairs of connections as integers (2-3, 5-1, 8-7).
2. The connections are transitive, so adding 2-3, 3-5, and 5-7 menas that 2-7 is also connected.
3. Once a transitive connection exists, adding the direct connection (2-7) is redundant and therefore ignored.

THIS IS THE SECOND ALGORITHM APPROACH THAT THE CHAPTER PROPOSES: Quick Union Algorithm (the first was "Quick Find" Algorithm).

In the Quick Union algorithm: a) each index (the left connection, and the right connection) are traversed to their roots (see below)* b) finally, the left root index is then assigned to the right root index

• To traverse each index to its root:

public int RootOfTreeFor(int index) { var valueFromIndex = _intArray[index];

// from index, get value, then treat it as index to get a new array value, UNTIL THEY MATCH
while (valueFromIndex != _intArray[valueFromIndex])
{
    valueFromIndex = _intArray[valueFromIndex];
}
return valueFromIndex;

}