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).

Answer 1

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.

Answer 2

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