Thread: quick union algorithm confusion

  1. #1
    Registered User MartinR's Avatar
    Join Date
    Dec 2013
    Posts
    200

    Exclamation 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:

    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:
    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

  2. #2
    Registered User
    Join Date
    Apr 2021
    Posts
    12
    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.

  3. #3
    Registered User
    Join Date
    Apr 2021
    Posts
    23
    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.
    Last edited by erikkonstas; 05-09-2021 at 06:43 PM.

  4. #4
    Registered User MartinR's Avatar
    Join Date
    Dec 2013
    Posts
    200
    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`

  5. #5
    Registered User
    Join Date
    Apr 2021
    Posts
    23
    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.

  6. #6
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,907
    Code:
    ...
        printf("\n");
        fflush(stdout);
        }
    Fun fact - the '\n' flushes the output buffer, so the fflush will never do anything.

  7. #7
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    945
    Quote Originally Posted by Click_here View Post
    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).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with quick sort algorithm
    By Bratwurst in forum C Programming
    Replies: 2
    Last Post: 12-27-2013, 02:55 PM
  2. Quick Union Algorithm
    By Andr3w in forum C Programming
    Replies: 3
    Last Post: 11-14-2011, 12:59 PM
  3. Help me on Quick Sort algorithm
    By chatterjee in forum C Programming
    Replies: 21
    Last Post: 07-19-2009, 01:40 PM
  4. Quick Algorithm Question
    By cjwenigma in forum C++ Programming
    Replies: 3
    Last Post: 11-01-2007, 10:39 AM
  5. if union could...
    By black in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2002, 08:34 AM

Tags for this Thread