Sorting strings in C

general
,
1

I was trying to sort c-strings using qsort().
Below is the comp function.

> int comp(const void *a,const void *b)
> {const char **ia=(const char **)a; 
> const char **ib=(const char **)b; 
> return strcmp(*ia,*ib); }

In main

char *b[6];
 for(int i=0;i<6;i++)
 b[i]=new char[6];
 for(int i=0;i<6;i++)
 strcpy(b[i],"");

The qsort function works in this case
where the call given to qsort was

size_t strings_len=sizeof(b)/sizeof(char *);//since the array is of char*s
 qsort(b,strings_len,sizeof(char*),comp);

here

strings_len=sizeof(b)/sizeof(char*);

However, if in main() we have

char b[6][6];
for(int i=0;i<6;i++)
strcpy(b[i],"");

and then we call qsort() as given above a SIGSEGV occurs.Whats the difference in the two?Isn’t b[i] a pointer to the c string?

1 Like
2

It is because, sizeof(b) is different in both cases (and hence, strings_len).

Case 1: char *b[6];

In this case, sizeof(b) is 24. This is because, b is an array of pointers. Each pointer takes 4 bytes and there are 6 such pointers. So, total = 4*6 = 24 bytes. So, string_len will be 24/sizeof(char *) = 6.

Case 2: char b[6][6];

In this case, sizeof(b) is 36. This is because, b is a 2D array of characters. Each character takes 1 byte and there are 6*6 = 36 such characters. So, total = 1*36 = 36 bytes. So, string_len will be 36/sizeof(char *) = 9.

Now, string_len is the number of elements in the array (which actually is 6 strings, but you get 9 for case 2). Hence, the segmentation fault.

NB: Since char * is a pointer, it is storing an address. So, it needs 4 bytes of storage. So, sizeof(char *) is always 4. (All these assuming a 32-bit gcc compiler.)

1 Like
3

The thing is that when you declare static 2D array <type> a[ROWS][COLUMNS] it’s not <type>** ,it’s totally different type (it’s actually <type>(*)[COLUMNS], but if it confuses you, don’t worry). The thing is even though we see this as a matrix it’s linearly laid out in memory. So size of one object of a is actually COLUMNS*sizeof(type), so if you pass a as an argument to a function you always have to specify width of one element as explained before. So size_t width argument of qsort() will be 6*sizeof(char) most likely resulting in 6. And when you dereference pointers in compare function you do it like this

int compare(const void* pa, const void* pb)
{
     char* a = (char*) pa, *b = (char*) pb;
     return strcmp(a,b);
}

because you deal with elements of your array b[6][6], which are arrays of 6 characters.

1 Like
4

Thanks for the answer though I had found this mistake afterwards .However,if I say that in
case 2:
we have qsort(b,6,sizeof(char*))
then also it doesn’t work.
Why?

1 Like
5

Thanx buddy:) This was exactly what I was looking for,the compare function.

6

the third parameter in qsort is “size of each element in the array”. Now, in this case, each “element” itself is a character array. So, its size will be the number of bytes taken by that array, which is 6. So, the correct way is qsort(b, 6, 6*sizeof(char *), compare); or equivalently, qsort(b, 6, sizeof(b[0]), compare);