Thread: sorting 2D string array

  1. #1
    Registered User sureshhewa's Avatar
    Join Date
    May 2008
    Location
    sri lanka
    Posts
    13

    Post sorting 2D string array

    Please tell me how to sort 2D string array according to the alphabetical order.

    eg:

    cat
    rat
    dog
    ram

    Answer must be:

    cat
    dog
    ram
    rat

    please notice that i know how to sort a integer array. but i have no idea of sorting string array,please help me

  2. #2
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    You can compare char's to eachother just like ints. Because a char is just an int.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You can sort integers easily because you can test if (a < b). To sort strings all you have to do is make it so that you can do the equivalent a < b test.
    In C, you'll have to make do with writing a LessThan function. Then you can do this:
    Code:
    if (LessThan(a, b))
    Now all you have to do is write a function called LessThan. Fortunately this can easily be achieved by using an existing function called strcmp.
    Now if you can sort integers, you can sort strings, or anything else that you can write a LessThan function for.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    Perhaps i should put this in another thread...but I ended up trying to do this problem here. My code was as follows:

    Code:
    #include <stdio.h>
    
    void sort(char *toSort[], int length);
    int lessThan(char*s, char*t);
    
    int main()
    {
        int i;
        
        char *strings[] = {"cat", "dog", "ram", "rat"};
        
        sort(strings, 4);
        
        //Print them out 
        for(i = 0; i < 4; i++)
        {
              printf("%s\n", *(strings + i));
        }
        
    }
    void sort(char *toSort[], int length)
    {
         int i, b;
         
        for(i = 0; i < 4; i++)  //loop through each element in the array
         {
               for(b = 0; b < 4; b++) //compare it to each element to see if it is shorter then it
               {
    
                     if(lessThan(*(toSort + i), *(toSort + b)) == 1) //ERROR HERE
                     {
                     /*
                     tmp = toSort[b];
                     toSort[b] = toSort[i];
                     toSort[i] = tmp;*/
                     }
                     
                                          
               }
               
         }  
    }
    
    int lessThan(char*s, char*t)
    {
        while(*(s++) == *(t++));
        if (*s == *t) //Same strings
           return 0;
        if (*s < *t)
           return 1; //Character has a lower internal character representation then *t
    }
    I have commented where I get my error. I am still new to C and trying to muddle myself through K&R's C book. They dont really explain passing array of pointer elements to functions in detail but it seems to bug out when I make my array offset a variable. I post this question here because it seems to be close to a solution to what the user asked but is a step short.

    So my question specifically, what am I doing wrong here when calling my lessThan function in the sort function?

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I'm not a fan of rewriting the standard library but if I had to I could write lessthan like so, such that every case returns a value.

    Code:
    int lessthan (const char * a, const char * b)
    {
        while (a && b && *a && *b && *a == *b) {
            ++a, ++b;
        }
        if (*a < *b) 
            return 1;
        else if (*a > *b)
            return -1;
        else
            return 0;
    }
    In your function, nothing is returned if *a > *b, which is a problem as you could very well run into such a case before the array is completely sorted.

    Check your algorithm also. That looks like an attempt at bubble sort to me and it doesn't look right. b and i are the same index, so you avoid comparing adjacent elements completely, and that is not a bubble sort.

  6. #6
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    Thanks for the help, but aside from my less then most efficient algorithm, my code won't even run. I am getting a segmentation fault at my if statement and I dont know why. Am I doing something wrong when passing arguments to lessThan in the sort function? I should be passing the address of the first char of the string for each string to lessThan...

  7. #7
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Well your crash is not in the if statement it's in the function called in the if statement. Anyways, you are passing the same pointer because i = b. So the while loop in lessThan will be infinite and you start referencing memory you shouldn't.

  8. #8
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    The loop in lessThan should stop when while gets to '\0' ?

    Using my function while sending the same string for both arguments works outside of this functions if statement for me.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    I was trying to emphasize that you could write a comparison function called say "LessThan", whose job would be solely to return true is the first argument was less than the second, and false otherwise.
    I then hinted that this could itself be written using strcmp, or it could use stricmp if you wanted to ignore character case.
    However for some reason you've decided to ignore using strcmp.

    When you get a compile error, never just say that you get an error! Always say exactly what the error is, and that also means a copy and paste, not a summary in your own words.

    Note that *(a + b) is the same as a[b] or b[a], using the array notation would be much shorter and clearer.

    The sort algorithm written will not quite work. Every pair of indexes are compared twice, and potentially swaps items twice. One of those swaps will do the right thing, and the other will put them back in the wrong order again. Another if-statement, or a modification to one of the loops will fix this.

    Also, to swap the strings around you will need to swap pointers, instead of ints. Just declare tmp as a char *.
    Don't use strcpy, in case someone mistakenly says that, because the array only contains pointers to string constants, and does not contain modifyable strings. For modifyable strings he would need to swap the * for more square brackets.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Quote Originally Posted by valaris View Post
    The loop in lessThan should stop when while gets to '\0' ?

    Using my function while sending the same string for both arguments works outside of this functions if statement for me.
    Sure, but have you tried it with comparing the same string location? That's what you are doing on the first iteration of your nested for loops. b=i=0 so *(toSort + i) = *(toSort + b). The problem is in your lessThan function. Put a printf in there if you want to be sure...

  11. #11
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    Ahh you are right...I guess my test to see if they are the same would never work because when s* becomes '\0' t would be ++'d and create an overflow. An initial test of if (s ==t) return 0; fixed this. As far as my sort algorithm iMalc I realize it's probably pretty bad...Im just a hobbyist really and know nothing of algorithms (but if you want to direct me to a specific to try and implement id give it a shot).

    Yes I know about the equality of array[i] <==> *(array + i) ...however after purchasing the K&R C book I am just trying to reinforce some pointer concepts in my head by using them explicitly when I can. This is the same reason for me writing a lessThan function as well instead of using standard functions, just as an attempt to learn C better ><

    Other then that...for the original poster if you cleanup the sort functionwhere lessThan comes back == 1 it should sort just fine.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Oh, I confusingly thought you were the original poster - OOPS!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User valaris's Avatar
    Join Date
    Jun 2008
    Location
    RING 0
    Posts
    507
    =-P No problemo. However you had mentioned that a simple change to my sort algorithm as it stands in my latest post would make the actual sorting work. Ive been looking at this for hours trying different things and I just can't get it to sort right. Ive looked up a few algorithms that seem to be "popular" such as bubble sort and selection sort, but cannot implement them correctly. If the changes are this simple perhaps can you look at my code and tell me where I am going wrong? Thanks

    I believe my logic under the if in sort() is what is throwing it off.

  14. #14
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Off the top of my head, bubble sort goes something like this:
    Code:
    for i equal to 0 up to array size
    	for each index up to array size - i
    		if index value greater than next index value
    			swap
    The basic idea is to pass over the array n times where n is the array size. The first pass will put the largest element at the end.

    Have you searched for sorting algorithms online? There are a number of sites that describe algorithms with animated graphics which can be a real help.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You might notice the link in my sig perhaps.

    The simplest thing you could do to fix what you have is to make b start at i+1 instead of 0. That way b is always greater than n.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compile Error that i dont understand
    By bobthebullet990 in forum C++ Programming
    Replies: 5
    Last Post: 05-05-2006, 09:19 AM
  2. 2D array sorting from min. to max.
    By khaled_helmy in forum C Programming
    Replies: 1
    Last Post: 10-14-2004, 02:17 PM
  3. lvp string...
    By Magma in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2003, 12:03 AM
  4. Something is wrong with this menu...
    By DarkViper in forum Windows Programming
    Replies: 2
    Last Post: 12-14-2002, 11:06 PM
  5. Classes inheretance problem...
    By NANO in forum C++ Programming
    Replies: 12
    Last Post: 12-09-2002, 03:23 PM