qsort() not sorting -:(

[yogeshmk]

I'm trying to write a program which sorts the strings entered by user.
I run it as

$./srt -sa dddd a ccc bb # -sa is options to the program s-string
a-ascending

and expect
a
bb
ccc
dddd
as output, for which I am using qsort() alongwith strcmp. However the
code simply prints back the strings as entered by user. I'm unable to
figure out what's wrong with the call to qsort().

Also when I compile the program, I get a warning saying something like
"argument 4 to qsort is of incompatible type" (not verbatim , I forgot
the actual message)

Here is a fragment of the code..

char **s = NULL;

</snip>
/*
*After stepping over argv[0], argv[1] (& possibly argv[2]), input
begins from argv
*/
s = argv+i;

if (option == STR)
{
qsort((void **) s, 0, argc-i,
(int(*)(char**, char**)) strcmp );
/* I have also tried (void*, void*)strcmp above, but get same
warning/output */
for (k=0; *(s+k); k++)
{
puts(*(s+k));
}
}
</snip>

I need help in figuring out what's wrong with qsort() call.

~yogesh

 

[Richard Heathfield]

yogeshmk said:

I'm trying to write a program which sorts the strings entered by user.
I run it as

$./srt -sa dddd a ccc bb # -sa is options to the program s-string
a-ascending

and expect
a
bb
ccc
dddd
as output, for which I am using qsort() alongwith strcmp.

Use this comparison function instead (pass its name as the fourth arg to
qsort). This will eliminate the need for any casting.

int cmpstr(const void *vp1, const void *vp2)
{
char * const *p1 = vp1;
char * const *p2 = vp2;
return strcmp(*p1, *p2);
}

However the
code simply prints back the strings as entered by user. I'm unable to
figure out what's wrong with the call to qsort().

The problem is that you are trying to sort argv's elements. The C language
definition does not give you permission to do that. You can modify argv
itself (i.e. point the whole thing elsewhere), and you can modify all the
characters from &argv[n][0] to the null terminator (n in the range 0 to
argc - 1, provided argc is positive). But you cannot modify argv[n] itself
to point elsewhere. If you try so to do, the behaviour is undefined. In
your case (and in mine, for I duplicated the behaviour on my system), the
runtime system appears to protect argv[n] from being written.

Solution: copy it to a separate array and sort that instead.

Also when I compile the program, I get a warning saying something like
"argument 4 to qsort is of incompatible type" (not verbatim , I forgot
the actual message)

Yeah. To get rid of that, use my comparison function (see above).

 

[Ben Pfaff]

char **s = NULL;
s = argv+i;
qsort((void **) s, 0, argc-i,
(int(*)(char**, char**)) strcmp );

I need help in figuring out what's wrong with qsort() call.

Everything.

1. The first argument to qsort() has type void *, not
void **. Your cast is unnecessary and bizarre.

2. The second argument to qsort() is the number of
elements to sort. You passed 0, so qsort() is not
actually going to sort any elements.

3. The third argument to qsort() is the number of bytes
in each element. You passed argc-i, which is not a
number of bytes at all. You should pass "sizeof *s"
or "sizeof (char *)", which is the size of one of the
elements in your array.

4. The fourth argument to qsort() has type int
(*compar)(const void *, const void *), but you passed
a function that doesn't have that type, casting it to
a third type (!). The function you passed isn't even
the right function for the job. You want something
like this instead:

int
compare_string_ptr (const void *a_, const void *b_)
{
const char **a = a_;
const char **b = b_;
return strcmp (*a, *b);
}

(I say "something like" because I can never remember
the rules for "const" and double-pointers. I just
write whatever comes to mind and let the compiler
complain if I get it wrong.)

 

[Ben Pfaff]

The problem is that you are trying to sort argv's elements. The C language
definition does not give you permission to do that. You can modify argv
itself (i.e. point the whole thing elsewhere), and you can modify all the
characters from &argv[n][0] to the null terminator (n in the range 0 to
argc - 1, provided argc is positive). But you cannot modify argv[n] itself
to point elsewhere. If you try so to do, the behaviour is undefined. In
your case (and in mine, for I duplicated the behaviour on my system), the
runtime system appears to protect argv[n] from being written.

It's not a matter of any kind of "protection". He passed 0 as
the "count" argument to qsort. That's not going to sort
anything.

 

[Richard Heathfield]

Ben Pfaff said:

The problem is that you are trying to sort argv's elements. The C
language definition does not give you permission to do that. You can
modify argv itself (i.e. point the whole thing elsewhere), and you can
modify all the characters from &argv[n][0] to the null terminator (n in
the range 0 to argc - 1, provided argc is positive). But you cannot
modify argv[n] itself to point elsewhere. If you try so to do, the
behaviour is undefined. In your case (and in mine, for I duplicated the
behaviour on my system), the runtime system appears to protect argv[n]
from being written.

It's not a matter of any kind of "protection". He passed 0 as
the "count" argument to qsort. That's not going to sort
anything.

Bizarre. I wrote my own code, which got the count right for qsort, and which
nevertheless refused to sort the argv array. To ensure that I had got the
code "right" (in the sense that, had it not been argv, it would sort), I
hacked it to sort a different array, and it worked fine. I tested argv
again, and it didn't sort. I tested the replacement again, and it worked. I
concluded that the runtime system was stopping me from sorting argv.

I then read your reply, which prompted me to re-re-test with argv, and it
worked!

/me is puzzled. Undefined behaviour is truly odd - or I did something screwy
partway through the process. Or, of course, both.

 

[yogeshmk]

The problem is that you are trying to sort argv's elements. The C language
definition does not give you permission to do that. You can modify argv
itself (i.e. point the whole thing elsewhere), and you can modify all the
characters from &argv[n][0] to the null terminator (n in the range 0 to
argc - 1, provided argc is positive). But you cannot modify argv[n] itself
to point elsewhere. If you try so to do, the behaviour is undefined. In
your case (and in mine, for I duplicated the behaviour on my system), the
runtime system appears to protect argv[n] from being written.

It's not a matter of any kind of "protection". He passed 0 as
the "count" argument to qsort. That's not going to sort
anything.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
);}return 0;}

Ok, I had got the params to qsort() wrong! Now after correcting,
qsort() sorts the input strings. But I still don't understand why
strcmp() does not work in qsort() (i used Richard's as well as Ben's
versions)

~yogesh

 

[Skarmander]

Ben Pfaff said:

The problem is that you are trying to sort argv's elements. The C
language definition does not give you permission to do that. You can
modify argv itself (i.e. point the whole thing elsewhere), and you can
modify all the characters from &argv[n][0] to the null terminator (n in
the range 0 to argc - 1, provided argc is positive). But you cannot
modify argv[n] itself to point elsewhere. If you try so to do, the
behaviour is undefined. In your case (and in mine, for I duplicated the
behaviour on my system), the runtime system appears to protect argv[n]
from being written.

It's not a matter of any kind of "protection". He passed 0 as
the "count" argument to qsort. That's not going to sort
anything.

Bizarre. I wrote my own code, which got the count right for qsort, and which
nevertheless refused to sort the argv array. To ensure that I had got the
code "right" (in the sense that, had it not been argv, it would sort), I
hacked it to sort a different array, and it worked fine. I tested argv
again, and it didn't sort. I tested the replacement again, and it worked. I
concluded that the runtime system was stopping me from sorting argv.

I then read your reply, which prompted me to re-re-test with argv, and it
worked!

/me is puzzled. Undefined behaviour is truly odd - or I did something screwy
partway through the process. Or, of course, both.

Ooh, a schroedinbug. Or rather, an inverse schroedinbug. Don't see much of
those.

http://catb.org/jargon/html/S/schroedinbug.html

S.

 

[Ben Pfaff]

But I still don't understand why strcmp() does not work in
qsort() (i used Richard's as well as Ben's versions)

There's a theoretical, language-lawyer answer and a practical,
bits-and-bytes answer.

The theoretical answer is that strcmp is the wrong type of
function and therefore passing it to qsort as the comparison
function invokes undefined behavior.

The practical answer is that qsort passes the wrong kind of
pointer. It passes two pointers, each of which points to a data
item. In your case, the data items are "char *". So it's
passing a pointer to a char *, or a char ** (although it actually
passes it as type void *). You need to dereference that one
level, to get a char *, and pass that to strcmp.

 

[Ben Pfaff]

The practical answer is that qsort passes the wrong kind of
pointer. It passes two pointers, each of which points to a data
item. In your case, the data items are "char *". So it's
passing a pointer to a char *, or a char ** (although it actually
passes it as type void *).

I should have said, "as type const void *".

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

The problem is that you are trying to sort argv's elements. The C language
definition does not give you permission to do that. You can modify argv
itself (i.e. point the whole thing elsewhere), and you can modify all the
characters from &argv[n][0] to the null terminator (n in the range 0 to
argc - 1, provided argc is positive). But you cannot modify argv[n] itself
to point elsewhere. If you try so to do, the behaviour is undefined. In
your case (and in mine, for I duplicated the behaviour on my system), the
runtime system appears to protect argv[n] from being written.

It's not a matter of any kind of "protection". He passed 0 as
the "count" argument to qsort. That's not going to sort
anything.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
);}return 0;}

Ok, I had got the params to qsort() wrong! Now after correcting,
qsort() sorts the input strings. But I still don't understand why
strcmp() does not work in qsort() (i used Richard's as well as Ben's
versions)

strcmp char pointers. - pointer to the first character in the strings
to compare.

The compare function you give to qsort is passed /pointers/ to the
elements to be compared.
Now if you have an array of char *, as in this case with argv, that
compare function receives pointer to those array elements.
That is , it'll be char **. You don't want to pass that to strcmp.

To get to the strings you need to dereference the pointers passed to
your compare function.