sort array in C, return sorted indices

Question

I'm using an example from https://phoxis.org/2012/07/12/get-sorted-index-orderting-of-an-array/ where he returns the sort indices from a sort of an array, i.e.

3,4,2,6,8 returns 4,3,1,0,2 (+1 for each index in R). This is the equivalent of R's order function

I've translated his/her code to work as a function returning an array of sorted indices. The code gives the correct answer.

keeping track of the original indices of an array after sorting in C has a similar response, but as @BLUEPIXY warns, his solution doesn't work in all circumstances. I need something that will work in all circumstances, including ties.

however, the original author uses a global pointer, which causes a memory leak, and free() doesn't fix it. which I don't know how to do this without the global pointer.

How can I fix this memory leak, or at least return sorted indices in C that will always work?

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

/* holds the address of the array of which the sorted index
 * order needs to be found
 */
int * base_arr = NULL;
/* Note how the compare function compares the values of the
 * array to be sorted. The passed value to this function
 * by `qsort' are actually the `idx' array elements.
 */
static int compar_increase (const void * a, const void * b) {
    int aa = *((int * ) a), bb = *((int *) b);
    if (base_arr[aa] < base_arr[bb]) {
        return 1;
    } else if (base_arr[aa] == base_arr[bb]) {
        return 0;
    } else {
//  if (base_arr[aa] > base_arr[bb])
        return -1;
     }
}

int * order_int (const int * ARRAY, const size_t SIZE) {
    int * idx = malloc(SIZE * sizeof(int));
    base_arr = malloc(sizeof(int) * SIZE);
    for (size_t i = 0; i < SIZE; i++) {
        base_arr[i] = ARRAY[i];
        idx[i] = i;
    }
    qsort(idx, SIZE, sizeof(int), compar_increase);
    free(base_arr); base_arr = NULL;
    return idx;
}


int main () {
    const int a[] = {3,4,2,6,8};
    int * b = malloc(sizeof(int) * sizeof(a) / sizeof (*a));
    b = order_int(a, sizeof(a) / sizeof(*a));
    for (size_t i = 0; i < sizeof(a)/sizeof(*a); i++) {
        printf("b[%lu] = %d\n", i, b[i]+1);
    }
    free(b); b = NULL;
    return 0;
}

Answer 1

A straightforward approach without using a global variable can look the following way

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

int cmp_ptr(const void *a, const void *b)
{
    const int **left  = (const int **)a;
    const int **right = (const int **)b;

    return (**left < **right) - (**right < **left);
}

size_t * order_int(const int *a, size_t n)
{
    const int **pointers = malloc(n * sizeof(const int *));

    for (size_t i = 0; i < n; i++) pointers[i] = a + i;

    qsort(pointers, n, sizeof(const int *), cmp_ptr);

    size_t *indices = malloc(n * sizeof(size_t));

    for (size_t i = 0; i < n; i++) indices[i] = pointers[i] - a;

    free(pointers);

    return indices;
}

int main( void )
{
    const int a[] = { 3,4,2,6,8 };
    const size_t N = sizeof(a) / sizeof(*a);
    size_t *indices = order_int(a, N);

    for (size_t i = 0; i < N; i++) printf("%d ", a[indices[i]]);
    putchar('\n');

    free(indices);

    return 0;
}

The program output is

8 6 4 3 2 

As for the memory leak then it is due to overwriting the value of the pointer to redundantly allocated memory.

int * b = malloc(sizeof(int) * sizeof(a) / sizeof (*a));
b = order_int(a, sizeof(a) / sizeof(*a));

The memory allocation does not make sense.

Answer 2

The problem I see is that within main function - you are allocating pointer b some memory -

   int * b = malloc(sizeof(int) * sizeof(a) / sizeof (*a));

The next line calls order_int(...) that returns a pointer to already allocated memory -

  b = order_int(a, sizeof(a) / sizeof(*a));

Looking at the order_int function -

int * order_int (const int * ARRAY, const size_t SIZE) {
    int * idx = malloc(SIZE * sizeof(int));
    base_arr = malloc(sizeof(int) * SIZE);
    for (size_t i = 0; i < SIZE; i++) {
        base_arr[i] = ARRAY[i];
        idx[i] = i;
    }
    qsort(idx, SIZE, sizeof(int), compar_increase);
    free(base_arr); base_arr = NULL;
    return idx;
}

.. you see that idx has been already been allocated the correct memory.

I would suggest removing the malloc from b - see below.

  int * b = NULL;