QSORT function in C

Question

In the following code, once I remove the commented part which compares strings, I am getting a seg 11 fault. I am unable to understand why! Rest of the code is working fine. Any help is appreciated!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_scores_desc(const void* scorea, const void* scoreb){
int a = *(int*)scorea;
int b = *(int*)scoreb;
return a-b;
}

int compare_names(const void* namea, const void* nameb){
char** a = *(char**)namea;
char** b = *(char**)nameb;
return strcmp(*a,*b);
}

int main(int argc, char* argv[]){
int scores[7] = {456,234,65,563,67,19,100};
int i;
qsort(scores,7,sizeof(int),compare_scores_desc);
puts("\nThese are the scores in order : \n");
for(i=0;i<7;i++)
    printf("%i\n",scores[i]);
char *names[] = {"Krishna","Rama","Bhishma","Arjuna"};
/*qsort(names,4,sizeof(char*),compare_names);*/
puts("------------------");
puts("The names in order are : \n");
for(i=0;i<4;i++)
    printf("%s\n",names[i]);
return 0;
}

Answer 1

In compare_names(), you are inappropriately dereferencing the arguments after the cast. The types for the local variables are type char **, but you are casting the arguments as char ** and dereferencing that results in a char *.

namea and nameb are pointers to the elements of your array names[] declared in main(). That means, their types are actually pointer to char *. When you dereferenced these arguments but assigned them to a char **, you cause the local variable to treat the char * as a char ** (your compiler should have issued a diagnostic warning you about this problem). Now, you take a pointer value that is a char *, and dereference it when you pass it to strcmp(). This causes the program to treat sizeof(char *) bytes of the string as a pointer value for the strcmp() function. Since 4 or 8 (or whatever sizeof(char *) is) bytes consisting of printable characters reinterpreted as a pointer value rarely yields a valid pointer, when strcmp() tries to use those pointers, a segmentation fault occurs.

One possible fix is to not dereference when you initialize your local variables. However, the arguments are const void *, so you can avoid the cast altogether if you declare your local variables to be a pointer to a const type:

int compare_names(const void* namea, const void* nameb){
char* const * a = namea;
char* const * b = nameb;
return strcmp(*a,*b);
}

Note that your implementation of compare_scores_desc() fails if a - b results in signed integer overflow. For example, if a is INT_MAX and b is -1. You should fix your implementation to work for all cases.

int compare_scores_desc(const void* scorea, const void* scoreb){
const int *a = scorea;
const int *b = scoreb;
return (*a > *b) - (*a < *b);
}

Answer 2

The problem is in your string comparison function, and here is probably the minimal way to fix it:

int compare_names(const void* namea, const void* nameb){
char* a = *(char**)namea;
char* b = *(char**)nameb;
return strcmp(a,b);
}

The namea and nameb arguments are pointers into the string vector. You understand this, which is why you used the char ** type.

However, all you have to do in the function is retrieve the char * pointers from that array. These char * pointers are already strings. You do not have to dereference them again; just pass them to strcmp.

Your original code has a constraint violation which requires a diagnostic. That should have tipped you off:

/* originally */
char** a = *(char**)namea; /* error: initialization from incompatible type */

You're dereferencing a char **, which produces char *, but you're storing that in a char ** again and dereferencing again, thereby wrongly treating the character data as a pointer.