Array sorting using pointer to pointer

[eager2no]

I want to sort an array of structures by a structure variable.
Sorting the structures directly works.
Re-wrote the merge sort routine to sort _pointers_ to the arrays so as to speed things up.
This doesn't work.

This is what I do:

// **** Declarations ****
#define BY_SEQNUM   0
#define BY_GENID    1
#define BY_LEN      2

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;

// **** Call to merge sort ****
    r_pt_by_SeqNum = (result **)malloc(resultcount * sizeof(result *));

    for(i = 0; i < resultcount; i++)    // initialize pointers
       r_pt_by_SeqNum[i] = &Results[i];  // (Results sequence is random) 

    SortResults(r_pt_by_SeqNum, resultcount - 1L, BY_SEQNUM);  // sort by seq_num

// **** 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);
	void msort_test3(result **ptpt, unsigned long low, unsigned long mid, unsigned long high);
	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);

        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 );
}
// **** End of code ****
// ********************* 

Sort does change the structure sequence in the array, but it doesn't seem to be sorted by anything.
Drives me crazy. I must be overlooking something.
Any help greatly appreciated.

[helios]

$10 say you're sorting the memory addresses.

[jpeg]

dangit, helios beat me to it :-(

Right now you're passing in pointers to pointers, and you don't seem to be dereferencing all the way to get to the actual values.

[eager2no]

helios,
Thank you for responding.
As a hobbyist programmer I wouldn't dare to bet :-)

So how should I correct the code to sort the ptpt[i] pointers to point to the structs in ascending seq_num order?

[eager2no]

jpeg,
I thought *ptpt[l]).seq_num dereferences to get the actual value...
So what should teh code look like instead?

[jpeg]

Well, IF I understand your program structure correctly you need to derefence it a bit more like this:

*ptpt[i].seq_num

But I'm not entirely sure by trying to trace through your code if that's how you have it set up or not.

edit: hmm, let me take a look again. I may be missing something in the way it's set up.

[helios]

Well, I'm not looking too hard at your code, but *(ptpt[i]) (in the comparison! If you do in the swap you'll lose your performance gain from pointers) should probably do it.

EDIT: If you're sorting based on a structure member, use ptpt[i]->member.

[eager2no]

helios,
I have already tried

if( ptpt[l]->seq_num <= ptpt[j]->seq_num

same (bad) result.

jpeg,
if( *ptpt[l].seq_num <= *ptpt[j].seq_num ){
causes a compiler error:
error: request for member `seq_num' in `*((+(l * 4ul)) + ptpt)', which is of non-class type `result*'|

[helios]

jpeg confused operator precedences. He meant to do what I did.

[eager2no]

*(ptpt[i])

Using that in the comparison yields a compiler error.
If you mean
(*ptpt[l]).seq_num
that is the syntax I used initially (then replaced it by ptpt[i]->seqnum), but no joy.
seq_num is unique, and what I get in the sequence is 8, 14, 3F, 20, ...

[helios]

He meant to do what I did.

By which I mean ptpt[i]->seq_num.

(*ptpt[i]).seq_num==ptpt[i]->seq_num

I don't know what to say. That should work.

[jpeg]

Did you replace it with ptpt[i]->seqnum or *ptpt[i]->seqnum?

[eager2no]

I currently have (*ptpt[j]).seq_num
ptpt[j]->seq_num yields the same bad result since the two forms are equivalent.

*ptpt[i]->seq_num seems to be wrong ('No symbol "ptpt" in current context')

I have probably tried all variations...

[jpeg]

I can't seem to compile your code and I'm not sure why. I'm getting an odd error at your for loops saying that it's expecting a constructor, destructor, or type conversion before any of the logical operators. I know I've seen this error before but I can't remember how to fix it. If I can figure out how to fix it and compile your code I may be able to figure out where the pointer problem is.

Here's the errors:

arraysort.cpp:22: error: expected constructor, destructor, or type conversion before '=' token
arraysort.cpp:24: error: expected unqualified-id before "for"
arraysort.cpp:24: error: expected constructor, destructor, or type conversion before '<' token
arraysort.cpp:24: error: expected constructor, destructor, or type conversion before '++' token
arraysort.cpp:27: error: expected constructor, destructor, or type conversion before '(' token

[helios]

Did you start C++ today? Don't you see there's no main()? Control structures can't be in global namespace.

[jpeg]

Yeah, I just realized that 5 minutes ago, lol. It's definitely a Friday. I completely missed the fact that there wasn't a main.

edit: and in my defense, it's not an error I get a lot, main is one of those things that's always in there. I probably haven't seen this error since my first program.

[satm2008]

And at a glance, I could tell you the program does not even compile.
At starting itself it misses an initialization for resoultCount;

unsigned long resultcount;

// **** Call to merge sort ****
    r_pt_by_SeqNum = (result **)malloc(resultcount * sizeof(result *));

    for(i = 0; i < resultcount; i++)    // initialize pointers
       r_pt_by_SeqNum[i] = &Results[i];  // (Results sequence is random) 

    SortResults(r_pt_by_SeqNum, resultcount - 1L, BY_SEQNUM);  // sort by seq_num 

Where is the initial value for resultCount which determines the number pointers (ie, result *) to be allocated for r_pt_by_SeqNum array of pointers.

The for statement in a global scope? (I assume you did not omit any code before you post it here). A declaration can appear in a global scope, but not a statement like for loop.

Without a memory allocation, the array/process would not go ahead any further. And it probably crash as soon as you start, as it attempts to an unallocated/junk memory address. r_pt_by_SeqNum would obviously have a junk address, definitely not NULL.

Check it out. Good luck :)

[eager2no]

I tried to post only as much of the code as necessary to describe the problem. The whole code is of course a lot bigger.
A simple main() and some initialization would allow the code to be run:

// declarations and merge sort as posted
// ...
#define SOMENUMBER   50
main()
{
   int SortResults(result **, unsigned long,  int);
   unsigned i;

    Results = (result *)malloc(SOMENUMBER * sizeof(result));
    if( Results == NULL ){	// Not enough memory for results
        printf("Not enough memory.\n");
        exit(-1);
    }

    for( i = 0; i < SOMENUMBER; i++)
        Results[i].seq_num = SOMENUMBER - i;  // to get seq_num reverse-sorted
    
    r_pt_by_SeqNum = (result **)malloc(SOMENUMBER * sizeof(result *));

    for(i = 0; i < SOMENUMBER; i++)    // initialize pointer array
       r_pt_by_SeqNum[i] = &Results[i]; 

    SortResults(r_pt_by_SeqNum, SOMENUMBER - 1L, BY_SEQNUM);  // sort by seq_num

    // AND IT DOESN'T SORT...
}

[eager2no]

Problem SOLVED.
Thank you al for helping.

To sum it up:

1. The routing was working correctly all along.

2. I isntructed Code::Blocks to watch
*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. A poster at cboard.cprogramming.com resolved the issue: s/he simply listed each array[i]->seq_num at the end of my test program, and found that the sorted seq_num values were correct (sorted).

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