qsort problem

**caduardo21** · 08-17-2005

Can someone tell me what am I doing wrong here? Thanks.

Code:

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

#define MAXINPUT 80
#define MAXLINES 200

int compare(const void *name1, const void *name2)
{
    return strcmp((char *)name1, (char *)name2);
}

int main(void)
{
    FILE *fp;
    char *p;
    char input[MAXINPUT];
    char *lineptr[MAXLINES];
    int i;
    int nlines = 0;

    printf("Name of file with names to sort: ");
    fgets(input, MAXINPUT, stdin);

    if ((p = strchr(input, '\n')) != NULL)
        *p = '\0';

    fp = fopen(input, "r");
    if (fp == NULL) {
        printf("%s could not be found...", input);
        getchar();
        return 1;
    }

    while ((fgets(input, MAXINPUT, fp)) != NULL) {
        p = (char *)malloc(1 * sizeof(input));
        strcpy(p, input);
        lineptr[nlines++] = p;
    }

    fclose(fp);

    qsort((void *)lineptr, nlines, sizeof(lineptr) / sizeof(lineptr[0]), compare);

    fp = fopen("names.txt", "w");
    if (fp == NULL) {
        printf("names.txt could not be created...");
        getchar();
        return 1;
    }

    for (i = 0; i < nlines; i++)
        fprintf(fp, "%s", lineptr[i]);

    fclose(fp);

    return 0;
}

**Dave_Sinkula** · 08-17-2005

I omitted some user input:

Code:

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

#define MAXINPUT 80
#define MAXLINES 200

int compare(const void *name1, const void *name2)
{
   char *const *x = name1;
   char *const *y = name2;
   return strcmp(*x, *y);
}

int main(void)
{
   FILE *fp;
   char *p;
   char input[MAXINPUT] = "file.txt";
   char *lineptr[MAXLINES];
   int i;
   int nlines = 0;

   fp = fopen(input, "r");
   if ( fp )
   {
      while ( fgets(input, MAXINPUT, fp) != NULL )
      {
         p = malloc(strlen(input) + 1);
         if ( p )
         {
            strcpy(p, input);
            lineptr[nlines++] = p;
         }
      }
      fclose(fp);
      qsort(lineptr, nlines, sizeof *lineptr, compare);
      fp = fopen("names.txt", "w");
      if ( fp )
      {
         for ( i = 0; i < nlines; i++ )
            fprintf(fp, "%s", lineptr[i]);
         fclose(fp);
      }
   }
   return 0;
}

Originally Posted by file.txt

baker
foxtrot
xray
gamma
able
charlie

Originally Posted by names.txt

able
baker
charlie
foxtrot
gamma
xray

It would also be prudent to free the memory that was allocated.

**caduardo21** · 08-18-2005

Thanks, Dave. Here's what my code looks like now:

Code:

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

#define MAXINPUT 80
#define MAXLINES 200

int compare(const void *name1, const void *name2)
{
    char *const *x = (char * const *)name1;
    char *const *y = (char * const *)name2;

    return strcmp(*x, *y);
}

int main(void)
{
    FILE *fp;
    char *p;
    char input[MAXINPUT];
    char *lineptr[MAXLINES];
    int i;
    int nlines = 0;

    printf("Name of file with names to sort: ");
    fgets(input, MAXINPUT, stdin);

    if ((p = strchr(input, '\n')) != NULL)
        *p = '\0';

    fp = fopen(input, "r");
    if (fp) {
        while ((fgets(input, MAXINPUT, fp)) != NULL) {
            p = (char *)malloc(strlen(input) + 1);
            strcpy(p, input);
            lineptr[nlines++] = p;
        }

        fclose(fp);
    }

    qsort((void *)lineptr, nlines, sizeof(*lineptr), compare);

    fp = fopen("names.txt", "w");
    if (fp) {
        for (i = 0; i < nlines; i++)
            fprintf(fp, "%s", lineptr[i]);

        fclose(fp);
    }

    for (i = 0; i < nlines; i++)
        free(lineptr[i]);

    return 0;
}

I hope I'm freeing the memory that was allocated correctly. I have a couple of questions for you or anyone else willing to answer them:

1- Why do I need to declare local variables in the compare function and why do they have to be of that specific type?

2- Why, when allocating memory with malloc, did you add one to the size returned by strlen?

3- Why didn't you use parentheses with sizeof?

Thanks

**nvoigt** · 08-18-2005

1) You are sorting an array of character pointers. The qsort function will call your compare function with the address of two of it's elements. So the parameter you get in the compare function is in fact a char** ( pointer to a pointer to character ) wrapped into a void*. Your function wants to compare the elements, so you have to get the element from the address by using the * operator on the ( pointer to pointer to character ) that you got.

Only you know what type each element is, so you have to cast the void pointers you get to a pointer to your element. Then you need to get the value this pointers point to and compare them.

2) A string is an array of characters terminated by a trailing zero character. The strlen function returns the number of characters up to the zero character, so if you need to reserve memory, you need to allocate one character more for the trailing zero.

**orbitz** · 08-18-2005

Since he is assigning to an object his casts are not necesary. It looks like he's trying to compile C on a C++ compiler. He should stop this at once.

**cboard_member** · 08-18-2005

http://www.eternallyconfuzzled.com/tuts/sorting.html - A great tutorial courtesy of Prelude

**Dave_Sinkula** · 08-18-2005

I'm glad nvoigt explained of the type already, so I'll just add a couple bits here and there.

Originally Posted by caduardo21

Code:

int compare(const void *name1, const void *name2)
{
    char *const *x = (char * const *)name1;
    char *const *y = (char * const *)name2;

    return strcmp(*x, *y);
}

1- Why do I need to declare local variables in the compare function and why do they have to be of that specific type?

You don't need to declare local variables, I just find the syntax easier. Also I do it to help avoid casting that may be erroneous and that hides any of the compiler's diagnostic messages. And as noted, in C the cast is not necessary in each assignment. But if you were to do this without the locals, you would need the casts.

Code:

int compare(const void *name1, const void *name2)
{
   return strcmp(*(char *const *)name1, *(char *const *)name2);
}

Note that I also choose not to cast away constness.

Originally Posted by caduardo21

2- Why, when allocating memory with malloc, did you add one to the size returned by strlen?

As already explained, it's to make room for the null terminator.

Originally Posted by caduardo21

3- Why didn't you use parentheses with sizeof?

The parentheses are necessary only for types; they are optional for objects. I choose not to use them with objects.

**caduardo21** · 08-18-2005

Why do you cast it to (char *const *) and not (const * char *) if the parameter for the compare function is const void?

**orbitz** · 08-18-2005

becuse const * char * is not a valid type.

**Dave_Sinkula** · 08-18-2005

Originally Posted by caduardo21

Why do you cast it to (char *const *) and not (const * char *) if the parameter for the compare function is const void?

Originally Posted by orbitz

becuse const * char * is not a valid type.

Well there's that.

Code:

int compare(const void *name1, const void *name2)
{
    return strcmp(*(char * const *)name1, *(char * const *)name2);
}

The thing being compared is passed via a pointer to const. This thing is a char*. Since it is a pointer to a pointer, and you want to compare what the pointer is pointing to (the string), you need to dereference it back to a pointer (to the string).

[I hope that was a correct explanation for my fellow pedants.]

Thread: qsort problem

Thread Tools

Search Thread

Display

qsort problem

Similar Threads

Someone having same problem with Code Block?

A question related to strcmp

WS_POPUP, continuation of old problem

Laptop Problem

Sorting problem.. well actually more of a string problem