How to "sort and modify" a list?

I am not sure if this subject was already treated but if it's the case I did not have the right keyword to find it.
In my code I extract a mapping so let's say: {5,0,23,2,2,0}. As you can see the values are not contiguous. What I would like to do is transform this mapping so that the returned list is {3,0,4,1,2,0}. Here 0 means that the element should be ignored. So basically what I want to do is renumber the elements based on their order without moving them in the list.

I did that by first creating a copy of my initial array and then sorting this copy using qsort from the stdlib C library. I also created a return_list in which my final mapping will be stored.

(the initial array is vec)

    elt_count = 1;
    for (size_t i = 0; i < n; i++) {
        if (copy[i] != 0) {
            for (size_t j = 0; j < n; j++) {
                if (copy[i] == vec[j]) {
                    return_list[j] = elt_count;
                    vec[j] = 0;
                    elt_count++;
                    break;
                }
            }
        }
    }

Here I use a counter to give the final mapping its values.

The problem is that this part of my method takes a lot of time and slows down my whole program while I was supposed to use the mapping to gain time.

I think I could store the position of each elements like this to try and improve the performances:

vec = (5,0,23,2,2,0)
5: (0)
23: (2)
2: (3,4)

However I am not sure how to implement this and then use it to gain performance.

Of course any other ideas to improve the performances are welcome !

One easy approach is to make a copy of your array including the indexes of the values:

int a2[n][2];
int zeros = 0;
for (int i = 0; i < n; i++) {
a2[i - zeros][0] = vec[i];
a2[i - zeros][1] = i;
zeros += (vec[i] == 0);
}

Now a2 is an array of length n-zeros, and its entries are the non-zero elements of vec paired with their indexes.

Now sort a2:

qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);

Using this comparison function:

int cmp_a2(const void *v, const void*w) {
const int *a = v;
const int *b = w;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return 1;
if (a[1] < b[1]) return -1;
if (a[1] > b[1]) return 1;
return 0;
}

Now you can replace the original elements in the array, using the original indices stored in the sorted a2:

for (int i = 0; i < n - zeros; i++) {
vec[a2[i][1]] = i + 1;
}

Here's all the pieces together as complete working example:

#include <stdlib.h>
#include <stdio.h>
void print_array(int *a, size_t n) {
for (int i = 0; i < n; i++)
printf("%s%d", i>0 ? ", " : "", a[i]);
printf("\n");
}
int cmp_a2(const void *v, const void*w) {
const int *a = v;
const int *b = w;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return 1;
if (a[1] < b[1]) return -1;
if (a[1] > b[1]) return 1;
return 0;
}
void order_array(int *vec, size_t n) {
int (*a2)[2] = malloc(n * 2 * sizeof(int));
size_t zeros = 0;
for (int i = 0; i < n; i++) {
a2[i - zeros][0] = vec[i];
a2[i - zeros][1] = i;
zeros += (vec[i] == 0);
}
qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
for (int i = 0; i < n - zeros; i++) {
vec[a2[i][1]] = i + 1;
}
free(a2);
}
int main(int argc, char *argv[]) {
int a[] = {5,0,23,2,2,0};
size_t n = sizeof(a) / sizeof(*a);
print_array(a, n);
order_array(a, n);
print_array(a, n);
}

You can use the the standard library functions qsort and bsearch to solve the problem. Here is a start:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define LEN(arr) (sizeof (arr) / sizeof (arr)[0])
int ElemDiff(const void *leftElemPtr, const void *rightElemPtr) {
return *(int *) leftElemPtr - *(int *) rightElemPtr;
}
int main(void)
{
int vec[] = {5, 0, 23, 2, 2, 0};
int sortedVec[LEN(vec)];
int i, *tail;
memcpy(sortedVec, vec, sizeof (vec));
qsort(sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
for (i = 0; i < LEN(vec); i++) {
tail = bsearch(vec + i, sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
assert(tail != NULL);
printf("%lld ", tail - sortedVec);
}
putchar('\n');
return 0;
}

This will print

4 0 5 2 2 0