using qsort() to sort strings

yunikon
yunikon used Ask the Experts™
on
can use qsort to sort integers but not strings.  can't get the compare function right.  eg;

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

int sortARRAY(const void *aa,  const void  *bb);

void main(void)
{
      int i;

      char *list[] = {"TOKYO", "LONDON", "ATHENS", "NEW_YORK"};

      qsort(*list, 4, sizeof(char), sortARRAY);
      for(i = 0; i < 4; i++)   {
             printf("\n%s\n", list[i]);
      }
      puts("\nEND \n\n");
      getch();
      return;
}

int sortARRAY(const void *aa, const void *bb)
{
      char *J, *K;

      J = (char *)aa;
      K = (char *)bb;
      int A;

      A = strcmp(J, K);
      if(A > 0)  return 1;
      else if
              (A < 0) return -1;
      else return 0;
}


output gives     KOTYO (yes)
                      LONDON
                      ATHENS
                      NEW_YORK

                      END

would like to sort & list filenames in a folder.
Thanks for your help.
-I
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
First you don't have to make the compare function bool(const void*, const void*), just make it bool(const char*, const char*) and then cast (int (*)(const void *,const void*)) when you call qsort. Second, your sizeof(char) is inappropriate whereas you're trying to sort strings. In your compare function, use strcmpn(const char*, const char*) to compare just up to the length of the shorter string. I don't think passing *list to qsort is correct, try list.
instead of sizeof() use need to use strlen() sorry I gotta go.
Commented:
The problem is that qsort operates on a block of memory. The block of memory you want it to sort is a block of pointers. The qsort function hands *pointers* to those pointers to the comparator function. So you need to pass list to qsort (the block of pointers) and then do a double dereference in sortARRAY:

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

int sortARRAY(const void *aa,  const void  *bb);

void main(void)
{
      int i;

      char *list[] = {"TOKYO", "LONDON", "ATHENS", "NEW_YORK"};

      qsort(list, 4, sizeof(char *), sortARRAY);
      for(i = 0; i < 4; i++)   {
            printf("\n%s\n", list[i]);
      }
      puts("\nEND \n\n");
      getch();
      return;
}

int sortARRAY(const void *aa, const void *bb)
{
      char **J, **K;

      J = (char **)aa;
      K = (char **)bb;
      int A;

      A = strcmp(*J, *K);
      if(A > 0)  return 1;
      else if
             (A < 0) return -1;
      else return 0;
}
Should you be charging more for IT Services?

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden using our free interactive tool and use it to determine the right price for your IT services. Start calculating Now!

Commented:
Perhaps some more explanation is in order. Because of the way you declared the array:

      char *list[] = {"TOKYO", "LONDON", "ATHENS", "NEW_YORK"};

what you have is an array of pointers. That is list points to a block of 4 pointers to character. Each of these pointers, in turn, points to some place in the constant pool that contains the string of its city. The array of pointers is a block of memory and can be sorted by qsort. The strings themselves, however, are not necessarily contiguous and cannot be sorted by qsort. To sort the array of pointers in list, you must pass list to qsort, as well as the number and width of each item. The width, in this case, is 4; the size of a pointer to character.

Now the compare function is handed pointers to these elements. So what sortARRAY will get is pointers to the pointers in list. Thus, to determine what string is associated with the argument passed in, you must dereference it twice.

On the other hand, if you had declared list like this:

      char list[][10] = {"TOKYO", "LONDON", "ATHENS", "NEW_YORK"};

it would have pointed to a block of memory that contained the strings themselves. Now list is a two dimensional array containing 4 strings of 10 bytes each. That is, there is a contiguous block of memory, 40 bytes long, that contains the stuff you want to sort. You would still pass list to qsort, but the width is now 10. The arguments passed to sortARRAY are still pointers to elements in list, but these elements are now the strings themselves; not pointers to the strings. So double dereferencing is no longer needed. With this declaration the program looks like this:

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

int sortARRAY(const void *aa,  const void  *bb);

void main(void)
{
      int i;

      char list[][10] = {"TOKYO", "LONDON", "ATHENS", "NEW_YORK"};

      qsort(list, 4, 10, sortARRAY);
      for(i = 0; i < 4; i++)   {
            printf("\n%s\n", list[i]);
      }
      puts("\nEND \n\n");
      getch();
      return;
}

int sortARRAY(const void *aa, const void *bb)
{
      char *J, *K;

      J = (char *)aa;
      K = (char *)bb;
      int A;

      A = strcmp(J, K);
      if(A > 0)  return 1;
      else if
             (A < 0) return -1;
      else return 0;
}

Author

Commented:
Thanks for your prompt answers.  Appreciate imladris's extra effort to really explain how the code works.  I now better understand qsort & pointers.   Would like to know if there is a book etc., that explains C & C++ as well as im does.  If so which is it?
Thanks again.

Commented:
Thanks yunikon.

I think there are many books that explain pointers very well.

The tricky bit, that is often not explained, is that declarations, such as the two different list declarations here, can have identical syntax (in both cases you can access elements of list as if it is a two dimensional array (list[i][j])), but a different underlying memory organization. In most cases it doesn't matter. But in some cases, such as dynamic allocation of memory, or using things like qsort, the underlying memory representation does matter, and in those cases it is critical that the various possibilities be understood.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial