tags:

views:

91

answers:

3

Hello,

I have a question regarding qsort.

This is a little bit weird, but my qsort function does not give me the correct output. The strange thing is that some of my compare functions are identical to my past projects but they don't give me the correct input at all. I am not sure how to test it.

For example:

int comp_name_asc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;
  return strcmp(prec1->name, prec2->name); 
}

int comp_name_desc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;
  return strcmp(prec2->name, prec1->name);
}

The second function should be descending order, but the result is identical: it's always in ascending order. I have checked to make sure the right function is entered at the right time. Rec is a typedef for a struct I made, which has a char * name parameter.

Also (MODIFIED to avoid overflow):

int comp_size_asc(const void *a, const void *b)
{
  const Rec *prec1 = (const Rec *) a;
  const Rec *prec2 = (const Rec *) b;

  if (prec1->byteSize > prec2->byteSize)
    return 1;
  else if (prec1->byteSize < prec2->byteSize)
    return -1;
  else
    return 0;
}

The result is completely weird, not ascending or descending (ie: 500, 515, 100, 200...). byteSize is of type off_t obtained by doing:

char *path; // Build the path
struct stat sb;
if (lstat(path, &sb) == 0) {
  // Read sb.st_size

I am really not sure how to debug this. All I know, is that the appropriate compare function is entered, and that some similar compare functions used to work in the past.

Any ideas or how I can debug this would be welcome. Thank you.

EDIT:

Adding the call to qsort:

int index = 0;
Rec **array = (Rec **) malloc(sizeof(Rec *) * capacity);
// Adds element to the array...
qsort(array, index, sizeof(Rec *), comp_name_desc);

(Every time an element is added to the array, index is incremented.)

Thanks.

EDIT:

The solution was given below. Thank you!

I had to change:

const Rec *prec1 = (const Rec *) a;

to

const Rec *prec1 = *(const Rec **) a;

because of how I defined my array. Thanks!

+1  A: 

You should never compare numbers by subtracting one from another. This will generally lead to overflow with signed types and will not work at all with unsigned types. The generic idiom for comparing numbers with tri-state result is the following

(a > b) - (a < b)

Otherwise, your comparison functions look fine, so the problem must be in the way you call the sorting function.

AndreyT
Thanks, I did not think about that. I will fix that with some if else if, else statement.
Jary
A: 

hearing what the behavior is, a hunch might be that the names are not actually the names, if strcmp() have the two arguments swapped and the results is still ascending. One suggestion might be to print out the names using printf, and also, reduce the names to 2 or 3 (number of records), to make it easier to debug and check for why it is behaving like that.

動靜能量
+1  A: 

Do you have an array of Rec, or rather an array of Rec pointers? I'm asking because the comparison function gets as parameters pointers into the array, not directly to your records.

Here is a demonstration of both ways:

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

typedef struct Rec {
  char *name;
} Rec;

/*
 * The pointers a and b point directly into the array,
 * where the Records themselves are.
 */
static int
cmp_Rec_by_name(const void *a, const void *b) {
  const Rec *rec1 = (Rec *)a;
  const Rec *rec2 = (Rec *)b;
  return strcmp(rec1->name, rec2->name);
}

/*
 * The pointers point directly into the array, where
 * not the records but pointers to them are. So they
 * are a pointer to a pointer to a record.
 */
static int
cmp_Rec_ptr_by_name(const void *a, const void *b) {
  const Rec *rec1 = *(Rec **)a;
  const Rec *rec2 = *(Rec **)b;
  return strcmp(rec1->name, rec2->name);
}

static void
sort_Rec(void) {
  Rec record[3];

  record[0].name = strdup("hello");
  record[1].name = strdup("world");
  record[2].name = strdup("how are you");
  qsort(record, 3, sizeof (Rec), cmp_Rec_by_name);

  for (int i = 0; i < 3; i++)
    printf("%s\n", record[i].name);
}

static void
sort_Rec_ptr(void) {
  Rec *(record[3]);

  record[0] = malloc(sizeof (Rec));
  record[1] = malloc(sizeof (Rec));
  record[2] = malloc(sizeof (Rec));
  record[0]->name = strdup("hello");
  record[1]->name = strdup("world");
  record[2]->name = strdup("how are you");
  qsort(record, 3, sizeof (Rec *), cmp_Rec_ptr_by_name);

  for (int i = 0; i < 3; i++)
    printf("%s\n", record[i]->name);
}

int
main() {
  sort_Rec();
  sort_Rec_ptr();
  return 0;
}
Roland Illig
Thank you very much, you are right, it should have been: const Rec *rec1 = *(Rec **)a; My problem has been fixed, Thank you very much!
Jary
With `const Rec rec1 = *(Rec *)a` you copy the whole record, but you don't need to. That's why I used the pointer pointer in `cmp_Rec_ptr_by_name`.
Roland Illig
Thank you very much!
Jary