c - How to qsort array of integer pointers?

Question

I have the following function that needs to return an array of pointers to a sorted list

int **list_elements_sorted(int *array, int n)
{
  if (n <= 0)
  {
    return NULL;
  }

  int **sorted_list = malloc(n * sizeof(int *));
  assert((sorted_list != NULL) && "Error! Memory allocation failed!");

  for (int i = 0; i < n; i++)
  {
    sorted_list[i] = &array[i];
  }

  qsort(sorted_list, n, sizeof(int *), comp_list_asc);

  return sorted_list;
}

And the comparator function

int comp_list_asc(const void *a, const void *b)
{
  int *A = *(int **)a;
  int *B = *(int **)b;

  return (A - B);
}

When I input an array E.G: 3 2 5 I'm getting the same output 3 2 5, what I'm doing wrong ?

void test_sorted_list_valid_3(void **state)
{
  int **output;

  int n = 3;
  int int_list[] = {3, 2, 5};
  int *int_list_sorted[] = {&int_list[1],
                            &int_list[0],
                            &int_list[2]};

  output = list_elements_sorted(int_list, n);

  assert_memory_equal(int_list_sorted, output, n);
  free(output);
}

标签： cqsort

Answer 1

You're subtracting pointers, instead of integers. The below change should work for you.

int comp_list_asc(const void *a, const void *b)
{
  int *A = *(int **)a;
  int *B = *(int **)b;

  return (*A - *B); // here's the change
}

As pointed out by @tstanisl, subtracting integers is prone to overflow/underflow errors. These can be addressed by changing the return statement like below.

return *A == *B ? 0 : *A < *B ? -1 : 1;