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.

Is this supposed to be pure C or C++?

No ++ stuff, just plain C.
I hope that doesn't disqualify me here...

Moved to the C forum then.

Quote:

---

Originally Posted by cpjust

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.

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*'

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

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?

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.

Quote:

---

Originally Posted by eager2no

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!).

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

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?

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

Quote:

---

Originally Posted by eager2no

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?

tabstop,
You sure know how to send a body scrambling to his compiler!

Quote:

---

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.

I can't believe this.

I am using Code::Blocks 8.02.
I added

Code:

---

*r_pt_by_SeqNum

---

to the watch window, just as I did before every time. It displays the member structures, and it still shows garbage for the member struct values except for r_pt_by_SeqNum[0], which is correct.

BUT adding a watch specifically for a single struct like this

Code:

---

*r_pt_by_SeqNum[i]

---

for any i shows the correct value for the sorted member variable seq_num.

So the code seems to work, but what I am telling Code::Blocks to watch is wrong.
Watching *r_pt_by_SeqNum shows all structures, but with wrong values.
???

tabstop,
thank you, thank you, thank you!

I still wasn't able to spot the error in your code that makes it sort incorrectly. However I would suggest trying to reproduce the problem with the minimum number of items possible, and then step through the code and see what it is doing.
Oh wait it was working afterall? Ah no wonder I couldn't find the bug.

Btw, When you're using integer keys and have lots of them, perhaps a few thousand, then FlashSort beats MergeSort. However if you do look into that, beware of the bugs in the version on neubert.net. You may want to copy the code from my website instead, see my sig.
RadixSort is another good popular one for when there are a large number of items, but FlashSort is simpler yet more tweakable with regards to the memory usage vs speed tradeoff.
Or if you want to stick to comparison based techniques, IntroSort is about as good as you can get in the general case.

Thank you all for helping.
And a big thank you again to tabstop for making me actually look at the values themselves instead of relying blindly on what the IDE showed me.

To sum it up:

1. The routine was working all along.

2. I instructed Code::Blocks to watch

Code:

---

*r_pt_by_SeqNum

---

as an array, and it did in fact list the structure array, but with wrong values, except for structure[0]. So I assumed a was seeing the right thing (the array), and that the routine was not working.

3. tabstop's post resolved the issue: I listed each array[i]->seq_num, and lo and behold, they had the right values.

4. So I either instructed Code::Blocks incorrectly about what to show, or this is a bug in Code::Blocks. It did list the structures of the array, but did not resolve what the individual pointers in the array pointed to, except for array item[0].

Now I can get on with the program.
Thank you all.