CSC300 / CSC402: QuickUnion [4/9]

  public int find(int p) {
    int root = p;
    while (root != id[root])
      root = id[root];





    return root;
  }

  public void union(int p, int q) {
    int pid = find(p); // loser
    int qid = find(q); // champion
    if (pid == qid) return;
    id[pid] = qid;

    count--;
  }

Output

       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 4  3:  9[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
 3  8:  8[0, 1, 2, 8, 3, 5, 6, 7, 8, 9]
 6  5:  7[0, 1, 2, 8, 3, 5, 5, 7, 8, 9]
 9  4:  6[0, 1, 2, 8, 3, 5, 5, 7, 8, 8]
 2  1:  5[0, 1, 1, 8, 3, 5, 5, 7, 8, 8]
 8  9: connected
 5  0:  4[0, 1, 1, 8, 3, 0, 5, 7, 8, 8]
 7  2:  3[0, 1, 1, 8, 3, 0, 5, 1, 8, 8]
 6  1:  2[1, 1, 1, 8, 3, 0, 5, 1, 8, 8]
 1  0: connected
 6  7: connected

N=          128 Union=  0.001 [Infinity] Connected=  0.000 [     NaN]
N=          256 Union=  0.000 [   0.000] Connected=  0.000 [     NaN]
N=          512 Union=  0.000 [     NaN] Connected=  0.000 [     NaN]
N=        1,024 Union=  0.000 [     NaN] Connected=  0.001 [Infinity]
N=        2,048 Union=  0.001 [Infinity] Connected=  0.002 [   2.000]
N=        4,096 Union=  0.001 [   1.000] Connected=  0.003 [   1.500]
N=        8,192 Union=  0.004 [   4.000] Connected=  0.014 [   4.667]
N=       16,384 Union=  0.023 [   5.750] Connected=  0.108 [   7.714]
N=       32,768 Union=  0.120 [   5.217] Connected=  0.610 [   5.648]
N=       65,536 Union=  0.529 [   4.408] Connected=  2.552 [   4.184]
N=      131,072 Union=  3.390 [   6.408] Connected= 18.097 [   7.091]
N=      262,144 Union= 17.161 [   5.062] Connected= 90.506 [   5.001]

Union is linear, Connected is linear