Thread: Using qsort to sort an array of strings

  1. #1
    Registered User
    Join Date
    Feb 2009
    Location
    Seattle
    Posts
    39

    Using qsort to sort an array of strings

    I understand that qsort will pass my function two char**'s and use it to sort my array of strings. Can someone help me with comparing two strings that were passed to my function as char**'s?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    
    static int sortstring( const void **str1, const void **str2 );
    typedef int (*funcptr)();
    
    int main (int argc, const char * argv[]) 
    {
    	int inx = 0;
    	funcptr p_sortstring;
    	char *starr[] = 
    	{
    		"dog",
    		"Arm",
    		"Cat",
    		"Eric",
    		"Bat",
    		"Fork",
    		"hello",
    		"Geroge",
    		"Mike",
    		"Alabama"
    	};
    	
    	size_t count = sizeof(starr)/sizeof(*starr);
    	qsort( starr, count, sizeof(char), p_sortstring );
    	for (inx = 0; inx < 10; inx++)
    		printf("%s ", starr[inx]);
    	
    	
    	
        
    	return 0;
    }
    
    static int sortstring( const void **str1, const void **str2 )
    {
    	int result = 0;
    	const char *rec1 = *str1;
    	const char *rec2 = *str2;
    	int val = strcmp(rec1, rec2);
    	
    	if ( val < 0 )
    	{
    		result = -1;
    	}
    	else if ( val > 0 )
    	{
    		result = 1;
    	}
    	else
    	{
    		result = 0;
    	}
    	
    	return result;
    }

  2. #2
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    The function passed to qsort takes two const void*, not const void**. Also, you can return any integer value, not just -1, 0 and 1, so you can just return the value of strcmp.

    Edit: Also, since you're comparing char*'s, the third parameter to qsort should be sizeof(char*)
    Last edited by Ronix; 05-09-2009 at 09:11 PM.

  3. #3
    Registered User
    Join Date
    Feb 2009
    Location
    Seattle
    Posts
    39
    Quote Originally Posted by Ronix View Post
    The function passed to qsort takes two const void*, not const void**. Also, you can return any integer value, not just -1, 0 and 1, so you can just return the value of strcmp.

    Edit: Also, since you're comparing char*'s, the third parameter to qsort should be sizeof(char*)
    Thanks for the help!

  4. #4
    Registered User
    Join Date
    Feb 2009
    Location
    Seattle
    Posts
    39
    Quote Originally Posted by Ronix View Post
    The function passed to qsort takes two const void*, not const void**. Also, you can return any integer value, not just -1, 0 and 1, so you can just return the value of strcmp.

    Edit: Also, since you're comparing char*'s, the third parameter to qsort should be sizeof(char*)
    After changing my call to qsort
    Code:
    qsort( starr, count, sizeof(char*), p_sortstring );
    and changing my function to
    Code:
    static int sortstring( const void *str1, const void *str2 )
    {
    	const char *rec1 = str1;
    	const char *rec2 = str2;
    	int val = strcmp(rec1, rec2);
    	
    		
    	return val;
    }
    I get the following runtime error when the program reaches the call to qsort:
    "EXC_BAD_ACCESS"

  5. #5
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    When you call qsort:

    Code:
    qsort( starr, count, sizeof(char*), p_sortstring );
    p_sortstring doesn't point to a valid function (And isn't of the same type of the function pointer that qsort accepts). Change the call to:

    Code:
    qsort(starr, count, sizeof(char*), sortstring);

  6. #6
    Registered User
    Join Date
    Feb 2009
    Location
    Seattle
    Posts
    39
    Quote Originally Posted by Ronix View Post
    When you call qsort:

    Code:
    qsort( starr, count, sizeof(char*), p_sortstring );
    p_sortstring doesn't point to a valid function (And isn't of the same type of the function pointer that qsort accepts). Change the call to:

    Code:
    qsort(starr, count, sizeof(char*), sortstring);
    Yup! Just realized that before coming back to this posting. This fixed it!
    Code:
    p_sortstring = sortstring;
    Thats funny, qsort is expecting a pointer to a function. Why does just passing the name of the function to qsort work? Is the name of a function synonymous to a pointer to a function?

  7. #7
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Yes.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    Code:
    static int sortstring( const void *str1, const void *str2 )
    {
            const char *rec1 = str1;
            const char *rec2 = str2;
            int val = strcmp(rec1, rec2);
    
            return val;
    }
    This function won't work for sorting your strings. The reason is that qsort() will pass pointers to your array members, each of which is a pointer to a char. Thus your sort function will see them as pointer to pointer to char. Since the function prototype requires const void*, a little trickery is needed:
    Code:
    static int sortstring(const void *str1, const void *str2)
    {
      /* one method: */
      char *const *rec1 = str1;
      char *const *rec2 = str2;
      return strcmp(*rec1, *rec2);
    
      /* another method: */
      return strcmp(*(char *const*)str1, *(char *const*)str2);
    }

  9. #9
    Registered User
    Join Date
    Feb 2009
    Location
    Seattle
    Posts
    39
    Quote Originally Posted by cas View Post
    This function won't work for sorting your strings. The reason is that qsort() will pass pointers to your array members, each of which is a pointer to a char. Thus your sort function will see them as pointer to pointer to char. Since the function prototype requires const void*, a little trickery is needed:
    Code:
    static int sortstring(const void *str1, const void *str2)
    {
      /* one method: */
      char *const *rec1 = str1;
      char *const *rec2 = str2;
      return strcmp(*rec1, *rec2);
    
      /* another method: */
      return strcmp(*(char *const*)str1, *(char *const*)str2);
    }
    Thanks!

    What would the syntax be if I were trying to compare structure members?

    Code:
    typedef struct car
    {
    	int year;
    	char model[50];
    }CAR_T, *CAR_P_T;
    
    static CAR_T cars[5] =
    {
    	95, "Toyota",
    	200, "Ford",
    	2009, "BMW",
    	2010, "Mercedes",
    	1990, "Delorian"
    };
    
    ...
    
    int main(void)
    {
         ...
         qsort(cars->model, count, sizeof(CAR_T), sort_cars);
         ...
    }
    
    static int sortstring(const void *str1, const void *str2)
    {
          /* tried this but compiler no likey */
      CAR_T *const *rec1->model = str1; /* compiler says this is a nested function. Also tried to cast str1 to CAR_T */
      CAR_T *const *rec2->model = str2;
      return strcmp(*rec1->model, *rec2->model);
    
     }
    Last edited by MSF1981; 05-11-2009 at 01:44 PM.

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    Quote Originally Posted by MSF1981 View Post
    What would the syntax be if I were trying to compare structure members?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct car
    {
      int year;
      char model[50];
    };
    
    static void print_cars(const struct car *cars, size_t n)
    {
      int i;
    
      for(i = 0; i < n; i++)
      {
        printf("%4d: %s\n", cars[i].year, cars[i].model);
      }
    }
    
    static int compar(const void *l, const void *r)
    {
      const struct car *left = l;
      const struct car *right = r;
    
      /* sort by model */
      return strcmp(left->model, right->model);
      /* or sort by year */
      return left->year < right->year ? -1 : 1;
    }
    
    int main (void)
    {
      struct car cars[] =
      {
        95, "Toyota",
        200, "Ford",
        2009, "BMW",
        2010, "Mercedes",
        1990, "Delorian"
      };
      size_t n = sizeof cars / sizeof *cars;
    
      puts("Before:");
      print_cars(cars, n);
      qsort(cars, n, sizeof *cars, compar);
      puts("After:");
      print_cars(cars, n);
    
      return 0;
    }

  11. #11
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    it is not necessary to make a function for type int (const void *, const void *)
    you can make any function and use type cast then

    output:

    Code:
    [guest@station eng]$ ./test
    dog
    Arm
    Cat
    Eric
    Bat
    Fork
    hello
    Geroge
    Mike
    Alabama
    Alabama
    Arm
    Bat
    Cat
    Eric
    Fork
    Geroge
    Mike
    dog
    hello
    [guest@station eng]$

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    Quote Originally Posted by MSF1981 View Post
    What would the syntax be if I were trying to compare structure members?
    If you are wanting to sort according to model as in your example, then you'd have
    Code:
    int sort_cars(const void *a, const void *b) {
    return strcmp(((CAR_T *)a)->model, ((CAR_T *)b)->model); }
    If you want to sort by year you'd do:
    Code:
    int sort_cars(const void *a, const void *b) {
    return ((CAR_T *)a)->year - ((CAR_T *)b)->year; }
    I don't see a need to define new variables/pointers inside the compare function.

  13. #13
    Registered User
    Join Date
    Sep 2007
    Posts
    1,012
    Quote Originally Posted by c.user View Post
    it is not necessary to make a function for type int (const void *, const void *)
    you can make any function and use type cast then
    This is wrong. The fact that it works for you doesn't mean the code is correct. If you pass the wrong function type, then qsort() will be calling a function incorrectly, and thus you'll have undefined behavior.

    If you're using a cast to shut a compiler up, it very often means you're doing something wrong.

  14. #14
    Registered User
    Join Date
    Apr 2009
    Location
    Russia
    Posts
    116
    cas, function qsort will throw pointers to const void to the Func, what is wrong ?
    You can't know which address void pointer includes (adress of pointer or address of a non-pointer object), because you can't get value from this address, e.g. if void *p, **q; and p = &q, you can't know what is q - its qualities, because it was defined by p pointer as a void value
    I must only prepare the Func for the work (it must take pointers to const void, and return - 0 +), and it does it
    Maybe you have thought that "any function" means ANY function, but it did not, any function for qsort format int (const void *, const void *), I meant that

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Most processor architectures use the same type of pointer to all types of data, but some don't. In those cases, pointers to different types may well need suitable conversion before you can use a void * to point to something else. If you fool the compiler into thinking that it doesn't need to make that conversion, then your code will not work.

    In the whole scheme of things, a thin wrapper that converts the pointer from const void * to some other type will be a tiny price to pay for better portability - and if there is no real conversion, the wrapper itself will be very thin. If we are calling something like strcmp, then the comparison of the strings in itself will be the major part anyways.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 2
    Last Post: 07-11-2008, 07:39 AM
  3. How to sort an array of pointers to structure
    By broli86 in forum C Programming
    Replies: 3
    Last Post: 06-30-2008, 02:52 PM
  4. Sorting strings in an array
    By JLan in forum C Programming
    Replies: 4
    Last Post: 11-29-2003, 05:10 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM