Sorting an array of strings in C

Question

I have an assignment I've been working on for a few hours now, and I can't seem to get it quite right. The assignment is to take a random number of names (from stdin), sort them, and then output them in alphabetical order. I can't find any sites online that handle this kind of sorting specifically, and have had no luck trying to implement qsort() into my code.

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


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

void main(int argc, char *argv[])
{
     char *input[] = {" "};
     char temp[20][20];
     int i = 0;
     int num = 0;
     int place = 0;
     int stringlen = sizeof(temp) / sizeof(char);


          printf("How many names would you like to enter? ");
          scanf("%d", &num);

          while (place < num)
          {
                printf("Please input a name(first only): ");
                scanf("%s", input[place]);
                printf("The name you entered is: ");
                printf("%s\n", input[place]);

                place++;
          }
          //qsort(temp, stringlen, sizeof(char *), stringcmp);      <-- just an idea I was messing with
          qsort(input, stringlen, sizeof(char *), stringcmp);

          printf("Names:\n");

          for(i=0; i<place; i++)
               printf("%s\n", input[i]);



          system("PAUSE");
          return(EXIT_SUCCESS);

}

The main problem is, when I go to output my code, I cannot use the char *input variable because of how its declared. The temp[] will display, but will not be sorted by qsort because it is not declared as a pointer. Any ideas?

Answer 1

You can't declare your input array like that. Since you know how many the user requires, you can dynamically allocate the array:

char **input = malloc(num * sizeof(char*));

Likewise, when you read your strings in, they need somewhere to go. Simply passing an uninitialized pointer to scanf is not okay. I suggest you define the maximum length of a name and have a temporary buffer for reading it:

const size_t MAX_NAME = 50;
char name[MAX_NAME];

...

for( i = 0; i < num; i++ )
{
    printf("Please input a name(first only): ");
    scanf("%s", name);
    input[i] = strdup(name);
}

[Note this does not prevent the user from overflowing the 'name' buffer. I used scanf for illustrative purposes only]

You seem to be passing the wrong array length to qsort. Try this:

  qsort(input, num, sizeof(char *), stringcmp);

When you are finished, you need to release memory for all the names and the array.

for( i = 0; i < num; i++ ) free(input[i]);
free(input);

could you explain the ** declarations throughout the code? I'm not sure what they're used for, although I know the function for stringcmp is a widely used algorithm, I have no idea how it works; I'm thrown off by the double de-reference markers.

Yep, in the case where I used it, I am telling C that to get a single character, I have to dereference a pointer twice. When you index a pointer, it's dereferencing. So I allocated an array by requesting a block of memory containing num * sizeof(char*) bytes. Because I assigned that pointer to a char**, the compiler knows that I am pointing to a chunk of memory that contains char* values.

If I ask for input[0] (this is the same as *input) it should look at the very start of that memory and pull out enough bytes to form a char*. When I ask for input[1], it skips past those bytes and pulls out the next bunch of bytes that form a char*. Etc... Likewise, when I index a char*, I am pulling out single characters.

In your stringcmp function, you have the following situation. You passed a void* pointer to qsort so it doesn't actually know the size of the data values stored in your array. That's why you have to pass both the array length AND the size of a single element. So qsort just blindly rips through this arbitrary-length array of arbitrary-sized values and fires off memory addresses that ought to contain your data for comparison. Because qsort doesn't know anything else about your array elements except where they are located, it just uses void*.

But YOU know that those pointers are going to be the memory addresses of two of your array elements, and that your array elements are char*. So you need the address of a char* (hence you cast the pointers to char**). Now you need to dereference these pointers when you call strcmp() because that function requires a char* (ie a value that points directly to the memory containing your string characters). That is why you use the * in strcmp(*ia, *ib).

Answer 2

One quick way to fix your program is to declare input as an array of pointers, like this:

char *input[20];

When you read names in, use tmp[place] for your buffer, and store the pointer into input, like this:

scanf("%19s", tmp[place]);
input[place] = tmp[place];

Now sorting the input should work fine.

This has a limitation of being limited to 20 lines of 20 characters max. If you learned about malloc in the class, you should be able to fix that by allocating your strings and the string array dynamically.