Analysis of Algorithms : An Active Learning Approach

6.7 PARTITIONING SETS 173

As was discussed, the initialize routine just sets each location of the Parent

array to 
1 to indicate that each value is in its own partition and each partition

has a size of 1.

Union( i, j )

i, j the partitions to join together

totalElements = Parent[i] + Parent[j]

if Parent[i] ≥ Parent[j] then

Parent[i] = j

Parent[j] = totalElements

else

Parent[j] = i

Parent[i] = totalElements

end if

TheUnion function is responsible for combining two partitions into one. It

begins by calculating the total number of elements that will be in the resulting

combined partition. It then adds the smaller partition to the larger one.

Remember that the partition sizes are stored as negative numbers, so the then

clause adds the i partition to the larger j partition, and the else clause adds the

j partition to the larger i partition.

6 5

8 1 3

2

11

4

7 9 12 10

Index

Parent

123 4 5 6 78910 1112

585 11–7–3161 3 –2 1

■FIGURE 6.11
A partition of the
numbers from 1 to
12 and the
associatedParent
array