CSC300 / CSC402: QuickFind [3/9]

  public int find(int p) {








    return id[p];
  }

  public void union(int p, int q) {
    int pid = find(p); // loser
    int qid = find(q); // champion
    if (pid == qid) return;
    for (int i = 0; i < id.length; i++)
      if (id[i] == pid) id[i] = 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, 8, 5, 6, 7, 8, 9]
 6  5:  7[0, 1, 2, 8, 8, 5, 5, 7, 8, 9]
 9  4:  6[0, 1, 2, 8, 8, 5, 5, 7, 8, 8]
 2  1:  5[0, 1, 1, 8, 8, 5, 5, 7, 8, 8]
 8  9: connected
 5  0:  4[0, 1, 1, 8, 8, 0, 0, 7, 8, 8]
 7  2:  3[0, 1, 1, 8, 8, 0, 0, 1, 8, 8]
 6  1:  2[1, 1, 1, 8, 8, 1, 1, 1, 8, 8]
 1  0: connected
 6  7: connected

N=          128 Union=  0.002 [Infinity] Connected=  0.000 [     NaN]
N=          256 Union=  0.001 [   0.500] Connected=  0.001 [Infinity]
N=          512 Union=  0.005 [   5.000] Connected=  0.000 [   0.000]
N=        1,024 Union=  0.004 [   0.800] Connected=  0.001 [Infinity]
N=        2,048 Union=  0.008 [   2.000] Connected=  0.000 [   0.000]
N=        4,096 Union=  0.010 [   1.250] Connected=  0.000 [     NaN]
N=        8,192 Union=  0.047 [   4.700] Connected=  0.000 [     NaN]
N=       16,384 Union=  0.163 [   3.468] Connected=  0.001 [Infinity]
N=       32,768 Union=  0.667 [   4.092] Connected=  0.001 [   1.000]
N=       65,536 Union=  2.857 [   4.283] Connected=  0.002 [   2.000]
N=      131,072 Union= 11.939 [   4.179] Connected=  0.002 [   1.000]
N=      262,144 Union= 46.604 [   3.904] Connected=  0.005 [   2.500]

Union is linear, Connected is constant