How to sort an `int **` array in C with native qsort

Question

I've been unable to find any question regarding this, and I think I'm going a bit crazy trying to figure this out.

I have the following code:

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

int cmp_int(const void *a, const void *b)
{
  return * (int *)a - * (int *)b;
}

int main(int argc, char *argv[])
{
  int n = 10;
  int **arr = calloc(n, sizeof(int *));
  srand((unsigned int) time(NULL));
  for (int i = n-1; i >= 0; i--) {
    arr[i] = calloc(1, sizeof(int));
    *(arr[i]) = rand() % 1000;
  }
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  qsort(arr, 10, sizeof(void *), cmp_int);
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  free(arr);
  return 0;
}

It's super basic, right? According to the manpage, the first argument is the pointer to the base element and the third argument is the size. However, I fail to get the array as a sorted result. I'm still really confused as to what the first and third argument to qsort should be since I suspect that that's where the fault is.

Any help is appreciated.

Thanks.

Edit: I should add that this code obviously does no error checking and that I was trying to test qsort with a double-pointer array of integers, so while yes I could use a regular array that was not the intended purpose of this code (it’s actually part of a bigger segment in a separate program).

Your comparison function is wrong. You're sorting an array of pointers to int. The comparison function will get pointers to those pointers. So the comparison should be return **(int **)a - **(int **)b; Notwithstanding that this ought to make the program work, it has many weirdnesses and problems. — Gene
– Gene, Commented Jan 24, 2020 at 5:16
@Gene that way you'll still suffer from overflow and UB. For example if a = 2147483640, b = -2147483642 then a - b = -14 (if the result wraps around) which is definitely not true. Same for a = -2147483642 and b = 2147483640 in which a - b will be positive. You need to do an unsigned subtraction to avoid overflow, and use the idiomatic compare function return (x < y) - (x > y). So the statement will become return (**(unsigned **)a < **(unsigned **)b) - (**(unsigned **)a > **(unsigned **)b)) — phuclv
– phuclv, Commented Jan 24, 2020 at 6:16
@chmike yeah my mistake. I meant unsigned when doing subtraction like return **(int **)a - **(int **)b;. But since that won't work you'll still have to do 2 comparisons like above in int and not unsigned int — phuclv
– phuclv, Commented Jan 24, 2020 at 8:16

Gene · Accepted Answer · 2020-01-24 05:40:50Z

5

Your program makes my head hurt. The reason you're not getting a correct sort is that the comparison function is wrong. It would need to be return **(int **)a - **(int **)b; to get a correct result.

However it's not worth fixing the problem that way. A list of at least some of the issues:

If you don't use argc and argv, don't declare them.
Cast in the srand call is unnecessary.
int comparison by subtraction is a bad idea because it can overflow.
calloc returns should always be checked for null (out of memory) results.
calloc isn't needed at all. Use a variable length array.
There's no need to allocate an array of pointers to ints. Just allocate an array of ints. Then your comparison works as-is.
The qsort call uses a hard constant 10 rather than n.
It's less error prone to give the element size by dereferencing the array name.
At the end you free the "spine" array but never the integer elements.
You should factor out a function to print the array.

Here's a version that addresses these.

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

int cmp_int(const void *va, const void *vb)
{
  int a = *(int *)va, b = *(int *) vb;
  return a < b ? -1 : a > b ? +1 : 0;
}

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

int main(void)
{
  int n = 10, a[n];
  srand(time(0));
  for (int i = 0; i < n; ++i) a[i] = rand() % 1000;
  print(a, n);
  qsort(a, n, sizeof a[0], cmp_int);
  print(a, n);
  return 0;
}

answered Jan 24, 2020 at 5:40

Gene

47.1k4 gold badges64 silver badges101 bronze badges

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

6 Comments

EsmaeelE Over a year ago

Is first issue (express argc, argv) may cause problem or just a suggest?

Jonathan Leffler Over a year ago

@EsmaeelE: if your compiler doesn't complain about unused variables when you use int main(int argc, char **argv) and then don't use argc or argv, then you haven't got enough warnings enabled. You need every bit of help you can persuade the compiler to give you.

S. Sharma Over a year ago

Hey there, thank you for the suggestions. I added a clarification to my post above (also I think I may have unintentionally edited your post on my phone).

EsmaeelE Over a year ago

@JonathanLeffler OK, I find it. gcc with -Wextra catch unused parameters.

EsmaeelE Over a year ago

@JonathanLeffler Is there any link or example that shows If we express function parameter and not use them (pass by not use in function body) especially for main, i.e. main(int argc, char **argv) cause problem? When main define in this way main(int argc, char **argv) and not pass any argument from console. Is any default argument pass to it?

|

David C. Rankin · Accepted Answer · 2020-01-24 07:03:01Z

The problem you are having is failing to account for one additional level of indirection created by allocating for a block of pointers with int **arr = calloc (n, sizeof *arr); and then allocating storage for a single int to each pointer with arr[i] = calloc (1, sizeof *arr[i]).

Since the int compare (const void *a, const void *b) compare function for qsort expects a pointer to the elements of the array being sorted, both a and b above will be pointer-to-pointer to int in your case requiring 2 levels of indirection be dereferenced before the integer values can be compared.

Rather than cmp_int, you actually need a cmp_int_ptr compare function. It can be written as:

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

(note: the two levels of indirection in the cast (int * const *)... which can also be written as (int **), but to correspond to the parameter type (const void *) the (int * const *) is proper)

Putting that in place, adding validations for each allocation and cleaning up your calloc type-size specification by using the dereferenced pointer itself to set type-size, you can do:

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

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

int main (void) {

    int n = 10;
    int **arr = calloc (n, sizeof *arr);

    if (!arr) {
        perror ("calloc-arr");
        return 1;
    }

    srand((unsigned int) time(NULL));

    for (int i = 0; i < n; i++) {
        if (!(arr[i] = calloc (1, sizeof *arr[i]))) {
            perror ("calloc-arr[i]");
            return 1;
        }
        *(arr[i]) = rand() % 1000;
    }

    for (int i = 0; i < n; i++)
        printf (" %d", *(arr[i]));
    putchar ('\n');

    qsort (arr, 10, sizeof *arr, cmp_int_ptr);

    for (int i = 0; i < n; i++) {
        printf (" %d", *(arr[i]));
        free (arr[i]);              /* don't forget to free your int allocated */
    }
    putchar ('\n');

    free(arr);                      /* now free pointers */
}

Example Use/Output

$ ./bin/qsortptrtoint
 654 99 402 264 680 534 155 533 397 678
 99 155 264 397 402 533 534 654 678 680

Look things over and let me know if you have questions.

Collectives™ on Stack Overflow

How to sort an `int **` array in C with native qsort

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related