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);
}

3 2 5 is not an array of pointers, it is an array of integers. And your sorted_list should be such — Eugene Sh.
– Eugene Sh., Commented Sep 29, 2021 at 13:40
I suspect (A-B) will always give you a positive result due to pointers being unsigned (aka the void type). But I'am not sure... — Jeroen3
– Jeroen3, Commented Sep 29, 2021 at 13:43
@EugeneSh. sorted_list is an array of pointers pointing to the array integers, array is my input — TheDayAfterDark
– TheDayAfterDark, Commented Sep 29, 2021 at 13:47
This does not make sense. You are expecting integers 3 2 5 to come out sorted (aren't you?), not their addresses. — Eugene Sh.
– Eugene Sh., Commented Sep 29, 2021 at 13:49

Fractal · Accepted Answer · 2021-09-29 14:50:36Z

5

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;

edited Sep 29, 2021 at 14:50

answered Sep 29, 2021 at 13:52

Fractal

8166 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

tstanisl Over a year ago

it's sensitive to integer overflows, i.e. *A == INT_MAX and *B == INT_MIN

Ted Lyngmo Over a year ago

Is this really all it took to fix the problem? I don't get it ...

Ted Lyngmo · Accepted Answer · 2021-09-29 14:13:34Z

You need to dereference A and B before subtracting in comp_list_asc.

You also sort the wrong thing, int_list (which is not an array of int*), instead of int_list_sorted.

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

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

    return *A - *B;      // dereference
}

int main() {
    int int_list[] = {3, 2, 5};

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

    int n = sizeof int_list_sorted / sizeof *int_list_sorted;

    // Sort the correct thing:

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

    // Print result to compare input and output:

    for(int i = 0; i < n; ++i) {
        printf("%d %d\n", int_list[i], *int_list_sorted[i]);
    }
}

Collectives™ on Stack Overflow

How to qsort array of integer pointers?

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related