Questions about qsort( ) to sort pointer to struct.

[PCHOME]

Hi!

I have questions about qsort( ). Is anyone be willing to help?

I use the following struct:
struct Struct_A{
double value;
...
} *AA, **pAA;

After allocating memory, I have pAA[n], and AA[n].
For all i, 0 <= i < n, pAA[i] = &AA[i] ;

I want to retrieve all the AA[i].value's according to the
value(decending order). So I want to sort.
Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
large),
I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value.
pAA[0]->value should be the biggest one.

I triied:
qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);
and
int comp(const void * row1, const void * row2)

struct Struct_A * Arow1
= (struct Struct_A *) row1;

struct Struct_A * Arow2
= (struct Struct_A *) row2;

if ( Arow1->value < Arow2->value) return (1);
elseif if if ( Arow1->value > Arow2->value) return (-1);
else return(0);
}
The code can run, but not in the way I need.

before sort:
pAA[0]->value = 0.688875
pAA[1]->value = 0.580136
pAA[2]->value = 0.379049
pAA[3]->value = 0.606478
pAA[4]->value = 0.742888
pAA[5]->value = 0.908687
pAA[6]->value = 0.969579
after sort
pAA[0]->value = 0.969579
pAA[1]->value = 0.908687
pAA[2]->value = 0.742888
pAA[3]->value = 0.606478
pAA[4]->value = 0.688875
pAA[5]->value = 0.379049
pAA[6]->value = 0.580136

and the following one works.
int comp(const void * row1, const void * row2)
{

struct Struct_A * Arow1
= *((struct Struct_A **) row1);

struct Struct_A * Arow2
= *((struct Struct_A **) row2);

if ( Arow1->value < Arow2->value) return (1);

else if ( Arow1->value > Arow2->value) return (-1);

else return 0;

}

Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A
*) row1"?
To me, Both row1 point to the same location "&AA[i]".
I am confused why the (struct Struct_A *) row1 version can not lead to
the correct result?

Is anyone able to use PLAIN English explain what is the difference?
and why dose the 2nd can not sort by "value"?

A sorting need to swap data.
The first one swap pAA[i] and pAA[j] if necessary.
What data will the (struct Struct_A *) row1 version indeed swap?

Thanks!

[Eric Sosman]

PCHOME wrote:

Hi!

I have questions about qsort( ). Is anyone be willing to help?

I use the following struct:
struct Struct_A{
double value;
...
} *AA, **pAA;

After allocating memory, I have pAA[n], and AA[n].
For all i, 0 <= i < n, pAA[i] = &AA[i] ;

I want to retrieve all the AA[i].value's according to the
value(decending order). So I want to sort.
Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
large),
I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value.
pAA[0]->value should be the biggest one.

I triied:
qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);
It would be better to use

qsort (pAA, n, sizeof *pAA, comp);

First, the `(void**)pAA' cast is wrong -- you will get
away with it on many machines, but it is wrong nonetheless
and there's no benefit in taking unnecessary risks. The
correct cast would be `(void*)pAA' but even that much is
unnecessary (assuming a prototype for qsort() is in scope,
which it certainly should be). In fact, with the prototype
the compiler will treat your original as equivalent to
`(void*)(void**)pAA'.

Second, `sizeof *pAA' is preferable to your original.
The original you wrote was correct, but `sizeof *pAA' offers
fewer opportunities to make silly errors. The compiler knows
what type `pAA' points to; let the compiler do the work of
figuring out the size.
and
int comp(const void * row1, const void * row2)

struct Struct_A * Arow1
= (struct Struct_A *) row1;
This would be right if you were sorting an array of
`struct Struct_A' objects, but you're not: you're sorting an
array of pointers to such objects. `row1' does not point
to a struct; it points to a pointer to a struct. Here's
what you need:

struct Struct_A * Arow1
= * (struct Struct_A **)row1;

That is: You convert `row1' from `void*' to a pointer to an
element of the array. Then since the array element is itself
a pointer to the ultimate struct, you apply `*' to the converted
array pointer to fetch the struct pointer.

Here's a simple rule: The type of the first argument to
qsort() is the type to which the comparison function's
arguments should be converted, give or take a `const'.
[...]
and the following one works.
int comp(const void * row1, const void * row2)
{

struct Struct_A * Arow1
= *((struct Struct_A **) row1);
Right. The things being sorted are pointers, and comp()
receives pointers to two of those things, hence the double
`**': comp() receives pointers to pointers.
Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A
*) row1"?
To me, Both row1 point to the same location "&AA[i]".

No, `row1' points to an element in the `pAA' array and
not to a struct at all. The array element points to a struct
in the `AA' array, but `row1' does not point there.

| | | |
+------+ +-------------+
row1 ---> |pAA[i]----> | AA[j] |
+------+ +-------------+
| | | |
+------+ +-------------+
| | | |
(You say that i==j when the sort begins, but that will not
remain true when qsort() rearranges the `pAA' array.)

--
Er*********@sun.com

[pete]

PCHOME wrote:

Hi!

I have questions about qsort( ). Is anyone be willing to help?

I use the following struct:
struct Struct_A{
double value;
...
} *AA, **pAA;

After allocating memory, I have pAA[n], and AA[n].
For all i, 0 <= i < n, pAA[i] = &AA[i] ;

I want to retrieve all the AA[i].value's according to the
value(decending order). So I want to sort.
Instead of sorting the whole AA[n](size_of(struct Struct_A) is very
large),
I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value.
pAA[0]->value should be the biggest one.

I triied:
qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp);
and
int comp(const void * row1, const void * row2)

struct Struct_A * Arow1
= (struct Struct_A *) row1;

struct Struct_A * Arow2
= (struct Struct_A *) row2;

if ( Arow1->value < Arow2->value) return (1);
elseif if if ( Arow1->value > Arow2->value) return (-1);
else return(0);

}
The code can run, but not in the way I need.

before sort:
pAA[0]->value = 0.688875
pAA[1]->value = 0.580136
pAA[2]->value = 0.379049
pAA[3]->value = 0.606478
pAA[4]->value = 0.742888
pAA[5]->value = 0.908687
pAA[6]->value = 0.969579
after sort
pAA[0]->value = 0.969579
pAA[1]->value = 0.908687
pAA[2]->value = 0.742888
pAA[3]->value = 0.606478
pAA[4]->value = 0.688875
pAA[5]->value = 0.379049
pAA[6]->value = 0.580136

and the following one works.
int comp(const void * row1, const void * row2)
{

struct Struct_A * Arow1
= *((struct Struct_A **) row1);

struct Struct_A * Arow2
= *((struct Struct_A **) row2);

if ( Arow1->value < Arow2->value) return (1);

else if ( Arow1->value > Arow2->value) return (-1);

else return 0;

}

Why does "*((struct Struct_A **) row1)" work?
but not "(struct Struct_A *) row1"?
To me, Both row1 point to the same location "&AA[i]".
I am confused why the (struct Struct_A *) row1 version can not lead to
the correct result?

Is anyone able to use PLAIN English explain what is the difference?
I wish I could.
and why dose the 2nd can not sort by "value"?

A sorting need to swap data.
The first one swap pAA[i] and pAA[j] if necessary.
What data will the (struct Struct_A *) row1 version indeed swap?

/* BEGIN output new.c */

AA[0].value is 0.688875
AA[1].value is 0.580136
AA[2].value is 0.379049
AA[3].value is 0.606478
AA[4].value is 0.742888
AA[5].value is 0.908687
AA[6].value is 0.969579

pAA[0]->value is 0.969579
pAA[1]->value is 0.908687
pAA[2]->value is 0.742888
pAA[3]->value is 0.688875
pAA[4]->value is 0.606478
pAA[5]->value is 0.580136
pAA[6]->value is 0.379049

/* END output new.c */

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>

#define NELEM 7

struct Struct_A {
double value;
struct Struct_A *next;
};

int comp(const void *arg1, const void *arg2);

int main(void)
{
struct Struct_A *AA, **pAA;
unsigned index;

AA = malloc(NELEM * sizeof *AA);
pAA = malloc(NELEM * sizeof *pAA);
if (AA == NULL || pAA == NULL) {
exit(EXIT_FAILURE);
}
AA[0].value = 0.688875;
AA[1].value = 0.580136;
AA[2].value = 0.379049;
AA[3].value = 0.606478;
AA[4].value = 0.742888;
AA[5].value = 0.908687;
AA[6].value = 0.969579;
puts("/* BEGIN output new.c */\n");
for (index = 0; index != NELEM; ++index) {
pAA[index] = AA + index;
printf("AA[%u].value is %f\n", index, AA[index] .value);
}
putchar('\n');
qsort(pAA, NELEM, sizeof *pAA, comp);
for (index = 0; index != NELEM; ++index) {
printf("pAA[%u]->value is %f\n", index, pAA[index]->value);
}
free(AA);
free(pAA);
puts("\n/* END output new.c */");
return 0;
}

int comp(const void *arg1, const void *arg2)
{
double value_1 = (**(struct Struct_A**)arg1).value;
double value_2 = (**(struct Struct_A**)arg2).value;

return value_1 > value_2 ? -1 : value_1 != value_2;
}

/* END new.c */
--
pete

[I_have_nothing]

Nice job!

[Keith Thompson]

"I_have_nothing" <dd******@yahoo.com.tw> writes:

Nice job!

What?

Don't assume that your readers have access to the article to which
you're replying. (It appears to have expired on my server.)

If you've been following this newsgroup, you've seen the following
many times:

If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.