Problem with Qsort
Author Message
Problem with Qsort

Hi!

I want to sort an dynamic array of strings by alphabetic order. To do
this I use Qsort like I show here:

typedef struct graph_name
{
char name[10];
BITMAP *graph; //BITMAP is typedef:ed by my graphic lib

Quote:
} GRAPH;

GRAPH *all_graph[32767];
int graph_ptr=0;

int sort_func (const void *a,const void *b) {
return(strcmp(a,b));

Quote:
}

int insert()
{
char string[10] = "";
GRAPH *new_graph;

gets(string);

new_graph = (GRAPH *)malloc(sizeof(GRAPH));
strcpy(new_graph->name,string);
graph_ptr++;
all_graph[graph_ptr] = new_graph;
qsort(all_graph,graph_ptr,sizeof(GRAPH),sort_func);

Quote:
}

The problem is that the array don't get sorted. If I print out the the
strings in order I'll get the order I entered them in (with insert). Why
is that?

TIA!
--

http://www.*-*-*.com/

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>I want to sort an dynamic array of strings by alphabetic order. To do
>this I use Qsort like I show here:

>typedef struct graph_name
>{
>      char name[10];
>      BITMAP *graph; //BITMAP is typedef:ed by my graphic lib
>} GRAPH;

>GRAPH *all_graph[32767];
>int graph_ptr=0;

>int sort_func (const void *a,const void *b) {
>return(strcmp(a,b));
>}

I think qsort sends a pointer to each object.  So I *think*
sort_func should be like this

int sort_func (const void *a,const void *b) {
return(strcmp((GRAPH *)(*a)->name,(GRAPH *)(*b)->name));

- Show quoted text -

Quote:
}

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

> >I want to sort an dynamic array of strings by alphabetic order. To
do
> >this I use Qsort like I show here:

> >typedef struct graph_name
> >{
> >      char name[10];
> >      BITMAP *graph; //BITMAP is typedef:ed by my graphic lib
> >} GRAPH;

> >GRAPH *all_graph[32767];
> >int graph_ptr=0;

> >int sort_func (const void *a,const void *b) {
> >return(strcmp(a,b));
> >}

> I think qsort sends a pointer to each object.  So I *think*
> sort_func should be like this

> int sort_func (const void *a,const void *b) {
> return(strcmp((GRAPH *)(*a)->name,(GRAPH *)(*b)->name));
> }

I suppose that Deltaman was pointing to the equality
of addresses of a structure and its first member.

if exists:

struct { int a; char b[10]; } s;

then:

&s == &(s.a).

So, both Deltaman's and Bruce' methods are equivalent, aren't they?

Victor.
--

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>Hi!

>I want to sort an dynamic array of strings by alphabetic order. To do
>this I use Qsort like I show here:

>typedef struct graph_name
>{
>      char name[10];
>      BITMAP *graph; //BITMAP is typedef:ed by my graphic lib
>} GRAPH;

>GRAPH *all_graph[32767];

OK, you have an array of pointers here, so the elements you are going to
sort are pointers to GRAPH

Quote:
>int graph_ptr=0;

>int sort_func (const void *a,const void *b) {
>return(strcmp(a,b));
>}

What sort_func gets passed is 2 pointers to elements of the array to be
sorted, i.e. in this case 2 pointers to pointers to GRAPH. These are
not suitable values to pass to strcmp()! Assuming you are soreting on name
try something like:

int sort_func (const void *a,const void *b)
{
return strcmp((*(GRAPH *const *)a)->name, (*(GRAPH *const *)b)->name);

Quote:
}

or make things clearer using temporaries:

int sort_func (const void *va,const void *vb)
{
GRAPH *const *a = va;
GRAPH *const *b = vb;

return strcmp((*a)->name, (*b)->name);

Quote:
}
>int insert()
>{
>      char string[10] = "";
>      GRAPH *new_graph;

>      gets(string);

You really should avoid using gets().

Quote:
>      new_graph = (GRAPH *)malloc(sizeof(GRAPH));

Always test the return value of malloc for failure. Also the cast is
redundant and is not considered good style in C.

Quote:
>      strcpy(new_graph->name,string);
>      graph_ptr++;
>      all_graph[graph_ptr] = new_graph;
>      qsort(all_graph,graph_ptr,sizeof(GRAPH),sort_func);
>}

You appear to be calling qsort() every time you add an element to the
array. That will be extremely inefficient. If possible read all the
elements in and then call qsort(). If not then qsort() may not be a sensible
approach (even a simple insertion would be faster).

--
-----------------------------------------

-----------------------------------------

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:
>I think qsort sends a pointer to each object.  So I *think*

That is correct.

Quote:
>sort_func should be like this

>int sort_func (const void *a,const void *b) {
>return(strcmp((GRAPH *)(*a)->name,(GRAPH *)(*b)->name));
>}

That will fail because *a and *b are illegal, you can dereference a
pointer to an incomplete type (like const void). See my other reply.

--
-----------------------------------------

-----------------------------------------

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:
>I suppose that Deltaman was pointing to the equality
>of addresses of a structure and its first member.

>if exists:

>    struct { int a; char b[10]; } s;

>then:

>    &s == &(s.a).

Well,   (int *)&s == &s.a

Quote:
>So, both Deltaman's

No, in Deltaman's method the value being passed to strcpy is a pointer
to a pointer to the struct, not a pointer to the struct so it isn't
pointing at the name string even given what you say above. It results
in undefined behaviour.

Quote:
>and Bruce' methods are equivalent, aren't they?

Bruce's method tries to dereference a pointer to const void which is
a constraint violation.

--
-----------------------------------------

-----------------------------------------

Fri, 07 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

> I think qsort sends a pointer to each object.  So I *think*
> sort_func should be like this

> int sort_func (const void *a,const void *b) {
> return(strcmp((GRAPH *)(*a)->name,(GRAPH *)(*b)->name));
> }

I *think* you're mistaken. The attempt to dereference the (const void*)
is illegal.

--

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>I *think* you're mistaken. The attempt to dereference the (const void*)
>is illegal.

Guess again.

(const void *) is a void pointer to a constant object (6.1.2.5 Types).

--

``Not only is UNIX dead, it's starting to smell really bad.'' -- rob

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

> writes:

>>I *think* you're mistaken. The attempt to dereference the (const void*)
>>is illegal.

>Guess again.

>(const void *) is a void pointer to a constant object (6.1.2.5 Types).

6.1.2.5:

"The void type comprises an empty set of values; it is an incomplete type
that cannot be completed."

So void * (and const void *) is a pointer to an incomplete type, not an
object type. In fact you can dereference a pointer to an incomplete type
(but the result isn't an lvalue). The result of dereferencing a const void *
pointer will be a void "value". The error occurs when you try to do anything
with that void value such as cast it to a non-void type or dereference it.

I misstated this in an earlier reply.

--
-----------------------------------------

-----------------------------------------

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>> I *think* you're mistaken. The attempt to dereference the (const
>> void*) is illegal.

> Guess again.

> (const void *) is a void pointer to a constant object (6.1.2.5 Types).

OK smart ass. You try compiling it and tell me what your compiler says.

--

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>>> I *think* you're mistaken. The attempt to dereference the (const
>>> void*) is illegal.

>> Guess again.

>> (const void *) is a void pointer to a constant object (6.1.2.5 Types).

>OK smart ass. You try compiling it and tell me what your compiler says.

>--

I don't understand why people in this newsgroup are so quick to
saying that (const void *) is illegal and bragging about how
good you are, please just tell me what it should be changed to.

Bruce

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

> >> I *think* you're mistaken. The attempt to dereference the (const
> >> void*) is illegal.

> > Guess again.

> > (const void *) is a void pointer to a constant object (6.1.2.5 Types).

> OK smart ass. You try compiling it and tell me what your compiler says.

A void pointer is an incomplete type, const or otherwise, and I do not
believe a pointer to an  incomplete type can be dereferenced.  Really,
how would the compiler know how to handle the data. You would need to
use a cast to produce a complete data type so the compiler knows how to
interpret the memory location.

Of course, once you use a cast on a void type, you no longer have a void
type.  A void type cannot be completed, only cast to some complete data
type.

--
********************************************

********************************************
It used to be:
Spare the rod and spoil the child.

Today it's:
Spare the rod to stay out of jail.

Sat, 08 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>> > (const void *) is a void pointer to a constant object (6.1.2.5 Types).

>> OK smart ass. You try compiling it and tell me what your compiler says.

system% cat > c.c
foo(const void *v)
{
}
system% cc -c c.c
system%

What you may not understand is that you can't dereference it:

system% cat > c.c
foo(const void *v)
{
*v = 0;
}
system% cc -c c.c
E "c.c",L3/C9(#232):    Can't dereference a pointer to void.

But you can cast the pointer into something that you can dereference:

system% cat > c.c
foo(const void *v)
{
*(int *)v = 0;
}
system% cc -c c.c
system%

Sad state of affairs when the 'smart ass' happens to be _right_.

--

``Not only is UNIX dead, it's starting to smell really bad.'' -- rob

Sun, 09 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

>>>> (const void *) is a void pointer to a constant object (6.1.2.5
>>>> Types).

>>> OK smart ass. You try compiling it and tell me what your compiler
>>> says.

> system% cat > c.c
> foo(const void *v)
> {
> }
> system% cc -c c.c
> system%

> What you may not understand is that you can't dereference it:

> system% cat > c.c
> foo(const void *v)
> {
> *v = 0;
> }
> system% cc -c c.c
> E "c.c",L3/C9(#232):    Can't dereference a pointer to void.

> But you can cast the pointer into something that you can dereference:

> system% cat > c.c
> foo(const void *v)
> {
> *(int *)v = 0;
> }
> system% cc -c c.c
> system%

> Sad state of affairs when the 'smart ass' happens to be _right_.

Precisely. If you re-read this thread you will see that my comment
referred to the code fragment presented thus...

int sort_func (const void *a,const void *b) {
return(strcmp((GRAPH *)(*a)->name,(GRAPH *)(*b)->name));

Quote:
}

..where I said that the attempt to dereference (const void*) was
illegal. This code will not compile. The expressions (*a) and (*b) are
surely illegal.

Rather than simply indicating that the code was flawed, I should have
shown how it might have been rectified.

--

Sun, 09 Jan 2000 03:00:00 GMT
Problem with Qsort

Quote:

> >>> I *think* you're mistaken. The attempt to dereference the (const
> >>> void*) is illegal.

> >> Guess again.

> >> (const void *) is a void pointer to a constant object (6.1.2.5 Types).

> >OK smart ass. You try compiling it and tell me what your compiler says.

> I don't understand why people in this newsgroup are so quick to
> saying that (const void *) is illegal and bragging about how
> good you are, please just tell me what it should be changed to.

Actually Lawrence Kirby has written a very good answer to this which
explains the standard quote and is very nice and *insult free*.

Stephan
(initiator of the campaign against grumpiness in c.l.c)

Sun, 09 Jan 2000 03:00:00 GMT

 Page 1 of 2 [ 28 post ] Go to page: [1] [2]

Relevant Pages