qsort() in Array of Pointer to String

This is a discussion on qsort() in Array of Pointer to String within the C Programming forums, part of the General Programming Boards category; I m trying to sort an Array of Pointer to String using qsort() . Result doesnt show the sorted string ...

  1. #1
    Registered User
    Join Date
    Jun 2007
    Posts
    99

    qsort() in Array of Pointer to String

    I m trying to sort an Array of Pointer to String using qsort() . Result doesnt show the sorted string , Have a look at the code

    Code:
    // qsort() in Array of Pointer to String 
    
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int cmp(const void *, const void *);
    
    main(void)
    {
        char *s[] = {
                       "Gaurav",
                       "Vaibhav",                   
                       "Garima",
                       "Amit"                     
                    };
                    
        qsort( (char*)s, 4 , sizeof(s[0]), cmp);
        
        int i = 0;
        while(i<4)
        {
            printf("\t%s\n",s[i]);
            i++;      
        }
                 
        getch();       
    }
    
    int cmp(const void *x, const void *y)
    {
        return(strcmp((char*)x,(char*)y));       
    }

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    qsort() passes pointers to each element to your compare function.

    If you have an array of ints, you'll be passed pointers to those ints. In your case you have an array of pointers. Therefore you'll be passeed pointers to pointers. Hence you should cast x and y to char **'s instead of char *'s, and then you need to dereference them. They may be passed into strcmp() in that manner.

  3. #3
    Registered User
    Join Date
    Jun 2007
    Posts
    99
    actually i have already tried my hand at bsearch() over Array of Pointer to String assuming Strings are sorted in assending order, and its working, here is the code

    Code:
    // bsearch() in Array of Pointer to String <assuming Sorted>
    
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int cmp(const void *, const void *);
    
    main(void)
    {
        char *s[] = {
                       "Amit",
                       "Garima",
                       "Gaurav",
                       "Vaibhav"                     
                    };
                    
        char *str = "Vaibhav";
        
        char **found = (char**)bsearch( (char*)&str, (char*)s, 4 , sizeof(s[0]) , cmp);
        
        if(found!=NULL)
                printf("Found!");
        else
                printf("Not Found!");
                 
        getch();       
    }
    
    int cmp(const void *x, const void *y)
    {
        return(strcmp((char*)x,(char*)y));       
    }
    here, too i used only pointer to char in my cmp() and not pointer to pointer to char and it was working, so y not on qsort() ?

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    Quote Originally Posted by vb.bajpai View Post
    here, too i used only pointer to char in my cmp() and not pointer to pointer to char and it was working, so y not on qsort() ?
    Possibly because your compiler optimized the code. Similar string constants might have been saved in the same exact position in the table. Since you have the same string written twice, the compiler might have set both pointers to point to the same address, thereby making the code take less memory since only one copy of the string would be stored instead of two.

    So with that in mind, the string you were searching for and the string that was inside the array might have been at the same exact address in memory. When you were comparing them, you would be comparing their addresses as strings. Even though that is not what you want to do, you would still get the same answer that they are equal, although the "equalness" means something different.

    It's important to note that on some compilers, this will not produce the same results. Some compilers will say that the string cannot be found, although most modern compilers will perform this optimization. You're playing with undefined bahavior by doing this, and therefore this code is wrong.

    See the fix in my first post.

  5. #5
    Registered User
    Join Date
    Jun 2007
    Posts
    99
    ok!

    so, my cmp() function is passed pointer to pointer to Strings stored.

    strcmp() function declaration says:-

    Code:
    int strcmp(const char *s1, const char *s2);
    this means strcmp() expects pointer to strings , so i need to dereference my pointers passed to cmp() only once. so i tried this

    Code:
    int cmp(const void *x, const void *y)
    {
        return(strcmp((char*)(*x),(char*)(*y)));       
    }
    but i m getting an error !

  6. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    You're being passed char **'s as void *'s. So as I said, cast them to char **'s. Then after they are cast as char **'s, then dereference them.

    What you're trying to do now is dereference them before casting. You can't do that. Dereference them after casting.

  7. #7
    Registered User
    Join Date
    Jun 2007
    Posts
    99
    thanx a ton! , it is working, here is what i hv done !

    Code:
    int cmp(const void *x, const void *y)
    {
        return(strcmp(*((char**)x),*((char**)y)));       
    }

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,047
    You should probably be casting x and y to (const char *). But other than that, you've got it.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Registered User
    Join Date
    Jun 2007
    Posts
    99
    yeah right

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ ini file reader problems
    By guitarist809 in forum C++ Programming
    Replies: 7
    Last Post: 09-04-2008, 06:02 AM
  2. RicBot
    By John_ in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2006, 06:52 PM
  3. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 09:19 AM
  4. Pros pls help, Pointer to array
    By kokopo2 in forum C Programming
    Replies: 7
    Last Post: 08-17-2005, 11:07 AM
  5. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 10:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21