Thread: sorting using pointer to pointer not working

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    9

    sorting using pointer to pointer not working

    Hi,

    I need to sort an array of structures by a structure member.
    Sorting the array elements directly works fine, but is not fast enough.
    So I re-wrote the merge sort routine to use an array of pointers pointing to the structures, and want to sort the pointers.
    This doesn't work. The pointers don't get sorted to point to the structures in aascending order of the member value.
    The sort does change the pointer values, but they don't get sorted by anything as far as I can see.

    Below is the part of the code that should be enough to test the problem.
    Code:
    // **** Declarations ****
    
    #define BY_SEQNUM   0  // which  struct member to sort by
    #define BY_GENID    1
    #define BY_LEN      2
    
    #define SOMENUMBER   50   // used in main() for initialization
    
    struct resultnode{
        unsigned long seq_num;
        unsigned long len;
        unsigned long Generation_ID;
        unsigned long generation_member_count;
    };
    typedef resultnode result;
    
    result *Results;
    result **r_pt_by_SeqNum;
    unsigned long resultcount;
    
    // **** merge sort routine ***
    
    int SortResults(result **ptpt, unsigned long thismany, int sorttype)
    {
        void partitioning(result **, unsigned long, unsigned long, int);
        partitioning(ptpt, 0L, thismany, sorttype);
        return(0);
    }
    
    void partitioning(result **ptpt, unsigned long low, unsigned long high, int sorttype)
    {
        void msort_test1(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);
        void msort_test2(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);  // not used in this test
        void msort_test3(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);  // not used in this test
        void partitioning(result **ptpt, unsigned long, unsigned long, int);
    
        unsigned long mid;
        if(low < high){
            mid = (low + high)/2;
            partitioning(ptpt, low, mid, sorttype);
            partitioning(ptpt, mid+1, high, sorttype);
    
            if(sorttype == BY_SEQNUM)
                msort_test1(ptpt, low, mid, high);  // this is the one tested here
            else if(sorttype == BY_GENID)
                 msort_test2(ptpt, low, mid, high);
            else if(sorttype == BY_LEN)
                msort_test3(ptpt, low, mid, high);
            else{ printf("Internal error\n"); exit(-1); }
        }
    }
    
    void msort_test1(result **ptpt, unsigned long low, unsigned long mid, unsigned long high)
    {
        unsigned long i,j,k,l;
        result **b;
    
        b = (result **)malloc(resultcount * sizeof(result *));
        if( b == NULL ){
            printf("Mem alloc error\n");
            exit(-1);
        }
    
        l = low;
        i = low;
        j = mid+1;
        while( (l <= mid) && (j <= high) ){
            if( (*ptpt[l]).seq_num <= (*ptpt[j]).seq_num ){
                b[i] = ptpt[l];
                l++;
            }
            else
            {
                b[i] = ptpt[j];
                j++;
            }
            i++;
       }
        if(l > mid){
            for(k = j; k <= high; k++){
                b[i] = ptpt[k];
                i++;
            }
        }
        else{
            for(k=l; k <= mid; k++){
                b[i] = ptpt[k];
                i++;
            }
        }
        for(k = low; k <= high; k++){
            ptpt[k] = b[k];
        }
        free ( b );
    }
    
    // ***some main stuff (I hope it'"s enough) to run the above ***
    main()
    {
        int SortResults(result **, unsigned long,  int);
        unsigned i;
    
        resultcount = SOMENUMBER;
    
        Results = (result *)malloc(resultcount * sizeof(result));
        if( Results == NULL ){
            printf("Not enough memory.\n");
            exit(-1);
        }
    
        for( i = 0; i < resultcount; i++)
            Results[i].seq_num = resultcount - i;  // to get seq_num reverse-sorted for the test
        
        r_pt_by_SeqNum = (result **)malloc(resultcount * sizeof(result *));
    
        for(i = 0; i < resultcount; i++)    // initialize pointer array
           r_pt_by_SeqNum[i] = &Results[i]; 
    
        SortResults(r_pt_by_SeqNum, resultcount - 1L, BY_SEQNUM);  //  // HERE WE GO
    
        // AND IT DOESN'T SORT...
    }
    
    // **** End of code ****
    // *********************
    I am totally stumped with this...

    Any help greatly appreciated.
    Last edited by eager2no; 09-19-2008 at 11:29 PM.

  2. #2
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Is this supposed to be pure C or C++?
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    9
    No ++ stuff, just plain C.
    I hope that doesn't disqualify me here...

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Moved to the C forum then.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by cpjust View Post
    Is this supposed to be pure C or C++?
    If it was C++, it wouldn't compile...
    Sir, you are committing many crimes here.
    First implicit main. Get rid of it.
    And then don't cast the return of malloc. It leads to subtle bugs in C.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    Sep 2008
    Posts
    9
    My real main doesn't look like that. It is just for testing.

    As for malloc, leaving it (void *) causes this compiler error:
    error: invalid conversion from `void*' to `result*'

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Oh, then you're compiling it as C++...
    You seemed to leave out that little detail. In that case, yes, the cast must be there.
    But you know, you should really post the real code, test code or not, because this code won't compile under C++ which is what you were compiling with...
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Are you sure that the copying around of items was what was slow in the first place? How did you measure that, and what type are the items?
    I would think that the large number of dynamic memory allocations during the sort would be hurting performance at least as much. Did you realise that all you need to do is allocate a second buffer the same size as the first, up front, and do no furthur allocations whilst it runs?
    You can also improve the performance by doing a four-way merge, or rather a "merge and then merge back" approach instead of a "merge and then copy back" approach.
    Any particular reason you chose Mergesort? How many items would it typically be sorting?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Sep 2008
    Posts
    9
    Elysia,
    The real code is a lot bigger.
    I initially sorted on the structures themselves, and all was dandy.
    The only two things I re-wrote was
    - access to the structures (using pointers this time)
    - the compare line in msort_test1, which used to read
    Code:
    if(res_pnt[l].seq_num <= res_pnt[j].seq_num){
    and put items in a buffer (b) that was (result *) and worked as expected,
    and now reads
    Code:
    if( (*ptpt[l]).seq_num <= (*ptpt[j]).seq_num ){
    puts items in a buffer (b) that is (result **) and doesn't seem to work.

    I added the main() part only to make it runnable (I confess I haven't even tested it, so you are probably right it isn't correct, but anything that calls the sort routine will do.)

    iMalc,
    The actual program measures the time it took to run.
    That was initially around a couple of thousand seconds, and is now down to about 30-40 secs (for the largest item count I tested, which was about 900,000).
    I chose Mergesort because I needed a fast method for sorting integers up to 4 bytes long.
    The number of items to be sorted can be anything between a couple of hundred to almost anything.
    Anything that speeds up the sort is most welcome, so thank you for pointing out "merge and then merge back" - I'll check that out.
    Last edited by eager2no; 09-20-2008 at 06:25 AM.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by eager2no View Post
    Elysia,
    The real code is a lot bigger.
    I initially sorted on the structures themselves, and all was dandy.
    The only two things I re-wrote was
    - access to the structures (using pointers this time)
    - the compare line in msort_test1, which used to read
    Code:
    if(res_pnt[l].seq_num <= res_pnt[j].seq_num){
    and put items in a buffer (b) that was (result *) and worked as expected,
    and now reads
    Code:
    if( (*ptpt[l]).seq_num <= (*ptpt[j]).seq_num ){
    puts items in a buffer (b) that is (result **) and doesn't seem to work.

    I added the main() part only to make it runnable (I confess I haven't even tested it, so you are probably right it isn't correct, but anything that calls the sort routine will do.)
    I'd thought that in your real code, which compiles, you'd have a proper main and would have copy n' pasted that, but I see you merely added some code in the post of yours to make it work or so.
    Anyway, remember that main always must return int. It should not return nothing, and not void or anything else, always int. What you did was omit int and thus getting implicit main which is invalid in C++ an deprecated in C89 (in other words - don't use it!).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Just to add that quicksort is generally better than mergesort. It is more efficient, even though it has a much worst case scenario complexity (O(n^2) vs O(nlogn)). You could try it with the previous working algorithm and compare

  12. #12
    Registered User
    Join Date
    Sep 2008
    Posts
    9
    Elysia,
    Point taken, and I assure you I haven't committed the sin mentioned in your post (and your sig).
    Apart from that, do you have an idea why that sort routine works on items directly, but not on items pointed to?

  13. #13
    Registered User
    Join Date
    Sep 2008
    Posts
    9

    Smile

    C_ntua,
    Thanks for pointing this out.
    I'll do that, but only as a last resort - I'd hate to accept defeat

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by eager2no View Post
    Elysia,
    Point taken, and I assure you I haven't committed the sin mentioned in your post (and your sig).
    Apart from that, do you have an idea why that sort routine works on items directly, but not on items pointed to?
    I added this to the end of your code:
    Code:
    for (i = 0; i < resultcount; i++) {
            printf("%lu\n", r_pt_by_SeqNum[i]->seq_num);
        }
    and I got the numbers from 1 to 50 in order. Is that not what you were expecting?

  15. #15
    Registered User
    Join Date
    Sep 2008
    Posts
    9
    tabstop,
    You sure know how to send a body scrambling to his compiler!
    Is that not what you were expecting?
    I was very much expecting it, but didn't get it.

    If this works as you say, I must have fouled up something else in the actual code.
    Will be back in a sec.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting the matrix question..
    By transgalactic2 in forum C Programming
    Replies: 47
    Last Post: 12-22-2008, 03:17 PM
  2. Problems passing a file pointer to functions
    By smitchell in forum C Programming
    Replies: 4
    Last Post: 09-30-2008, 02:29 PM
  3. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  4. Pointer validity check
    By Carlos in forum Windows Programming
    Replies: 6
    Last Post: 12-11-2003, 03:40 AM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM