quick union algorithm confusion

Hello,

I read Algorithms in C (3rd edition) by R.Sedgewick and I am a bit confused about the very first algorithm in the book, which aims to store connections between different nodes - so if the input for the program is 1 2 it means that first node is connected to the second. Here is the algorithm code:

Code:

---

#include <stdio.h>
#define N 10000
main() {
    int i, p, q, t, id[N];
    //init of the array
    for (i = 0; i < N; i++) id[i] = i;

  while (scanf(" %d %d", &p, &q) == 2) {
        //find operation   
        for (i = p; i != id[i]; i = id[i]) ;
    for (j = q; j != id[j]; j = id[j]) ;
    if (i == j) continue;
        //union operation
    id[i] = j;
    /* let's print out connection table */
    for (i = 0; i < 10; i++)
        printf("%d-",id[i] );
    printf("\n");
    fflush(stdout);
    }

 }

---

Here is the example input and output for the case when the input pairs pairs come in order 1-2 2-3 and so forth:

Quote:

---

0 1
1-1-2-3-4-5-6-7-8-9-
1 2
1-2-2-3-4-5-6-7-8-9-
2 3
1-2-3-3-4-5-6-7-8-9-
3 4
1-2-3-4-4-5-6-7-8-9-
4 5
1-2-3-4-5-5-6-7-8-9-
5 6
1-2-3-4-5-6-6-7-8-9-
6 7
1-2-3-4-5-6-7-7-8-9-
7 8
1-2-3-4-5-6-7-8-8-9-
8 9
1-2-3-4-5-6-7-8-9-9-

---

The author claims that for the input just provided above we get a straight line with N (9 in this case) pointing to N-1 which points to N-2 etc and here I agree. Then he claims that to execute the find operattion for object N the program has to follow N-1 pointers - here I don't agree. When N==9 the loop

Code:

---

for (i = p; i != id[i]; i = id[i]) ;

---

will get straight into the correct pointer and we terminate at the first check of

Code:

---

i != id[i]

---

. Do you agree?
Next. he says:

Quote:

---

Now suppose that the remainder of the pairs all connect N to some other object. The find operation for each of these pairs involves at least (N-1) pointers. The grand total for the M find operations for this sequence of input pairs is certainly greater than MN/2.

---

First of all I don't get what he understands by "remainder of the all pairs" but if they are those >N then I still don't get why the find operation for them would take N-1 pointers. Let's take N+1 as an exmaple here. This is 10 in our case and it was id[10] = 10 (initialized by the starup for loop) so where the N-1 comes from? :|

Thanks

You might want to fix your question. Even after fixing the declaration of main (must be "int main()" in standard C), the variable j is not declared; and you have a variable t that's not used anywhere. Post the code you actually compiled and ran to get that output.

Also, say explicitly what the code is supposed to do. I happen to have a copy of Algorithms in C on my shelf, but not everyone else will. My copy is the original edition though, from 1990, and does not have anything remotely like that as "the very first algorithm". It uses Euclid's algorithm for computing the GCD as the first algorithm and complete program, and the Sieve of Eratosthenes method for finding prime numbers as the first algorithm using arrays. So, even having a similar book on hand, I don't have any of the discussion surrounding this example. Most others won't, either.

Yeah... I happen to be experiencing Sedgewick's snippets from this very book (second edition, current university professor is using it) and his coding style is HORRENDOUS!!! Globals everywhere (in the name of "doing good information hiding" like there's no better and more obvious way, resulting in inability to have more than one instance of a data structure in your entire program), code causing segfaults, memory leaks, syntax errors and all other kinds of good stuff in completely unreadable code... I wouldn't blame OP for this, honestly.

I figured that out eventually...ugh, the problem is author describes code snippets and all of the sudden comes up with some *input* and *output* data example which can not be produced by this code he wrote... So from my original question - the statement I did 'will get straight into the correct pointer and we terminate at the first check is true from authors code snippet but is not true from the example he describes since in this case the 9th element will keep the reference to the 8th one, and 8th to the 7th etc.. Hence the amount of calls in indeed about `N`

Yep, that's exactly my point about Sedgewick. So I checked again, we're actually using the THIRD edition at university, and the thing where the text and the code differ a lot semantically is very prevalent... not to mention half of the time his code is completely nonsensical.

Code:

---

...
    printf("\n");
    fflush(stdout);
    }

---

Fun fact - the '\n' flushes the output buffer, so the fflush will never do anything.

Quote:

---

Originally Posted by Click_here

Code:

---

...
    printf("\n");
    fflush(stdout);
    }

---

Fun fact - the '\n' flushes the output buffer, so the fflush will never do anything.

---

Unless, of course, stdout is fully buffered (e.g., it doesn't point at an interactive device like a terminal).