qsort() not sorting -:(

Discussion in 'C Programming' started by yogeshmk, Jul 11, 2006.

  1. yogeshmk

    yogeshmk Guest

    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
     
    yogeshmk, Jul 11, 2006
    #1
    1. Advertising

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

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Jul 11, 2006
    #2
    1. Advertising

  3. yogeshmk

    Ben Pfaff Guest

    "yogeshmk" <> writes:

    > 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.)
    --
    "The fact that there is a holy war doesn't mean that one of the sides
    doesn't suck - usually both do..."
    --Alexander Viro
     
    Ben Pfaff, Jul 11, 2006
    #3
  4. yogeshmk

    Ben Pfaff Guest

    Richard Heathfield <> writes:

    > 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;}
     
    Ben Pfaff, Jul 11, 2006
    #4
  5. Ben Pfaff said:

    > Richard Heathfield <> writes:
    >
    >> 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.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Jul 11, 2006
    #5
  6. yogeshmk

    yogeshmk Guest

    Ben Pfaff wrote:
    > Richard Heathfield <> writes:
    >
    > > 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
     
    yogeshmk, Jul 11, 2006
    #6
  7. yogeshmk

    Skarmander Guest

    Richard Heathfield wrote:
    > Ben Pfaff said:
    >
    >> Richard Heathfield <> writes:
    >>
    >>> 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.
     
    Skarmander, Jul 11, 2006
    #7
  8. yogeshmk

    Ben Pfaff Guest

    "yogeshmk" <> writes:

    > 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.
    --
    Just another C hacker.
     
    Ben Pfaff, Jul 11, 2006
    #8
  9. yogeshmk

    Ben Pfaff Guest

    Ben Pfaff <> writes:

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

    > You need to dereference that one level, to get a char *, and
    > pass that to strcmp.



    --
    "Some people *are* arrogant, and others read the FAQ."
    --Chris Dollin
     
    Ben Pfaff, Jul 11, 2006
    #9
  10. yogeshmk wrote:
    > Ben Pfaff wrote:
    >> Richard Heathfield <> writes:
    >>
    >>> 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.
     
    =?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=, Jul 11, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. richard

    Re: qsort and structs and ptrs

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    0
    Views:
    406
    richard
    Aug 14, 2003
  2. Dimitris Mandalidis

    qsort mode-based sorting

    Dimitris Mandalidis, May 9, 2004, in forum: C Programming
    Replies:
    6
    Views:
    377
  3. sorting 2d arrays using qsort

    , Jun 11, 2005, in forum: C Programming
    Replies:
    23
    Views:
    1,718
    CBFalconer
    Jun 14, 2005
  4. Replies:
    6
    Views:
    755
  5. Cstudent

    sorting an array of strings using qsort

    Cstudent, May 10, 2009, in forum: C Programming
    Replies:
    1
    Views:
    503
    luserXtrog
    May 10, 2009
Loading...

Share This Page