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

You can compare char's to eachother just like ints. Because a char is just an int.

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.

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?

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.

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...

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.

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.

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.

Quote:

---

Originally Posted by valaris

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...

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.

Oh, I confusingly thought you were the original poster - OOPS!

=-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.

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.

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.