Solved

using qsort() to sort strings

Posted on 2003-10-21
6
661 Views
Last Modified: 2011-09-20
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
0
Comment
Question by:yunikon
  • 3
  • 2
6 Comments
 
LVL 4

Expert Comment

by:n_fortynine
ID: 9593962
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.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 9593973
instead of sizeof() use need to use strlen() sorry I gotta go.
0
 
LVL 16

Accepted Solution

by:
imladris earned 125 total points
ID: 9594116
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;
}
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 16

Expert Comment

by:imladris
ID: 9594187
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;
}
0
 

Author Comment

by:yunikon
ID: 9594956
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.
0
 
LVL 16

Expert Comment

by:imladris
ID: 9599281
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.
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now