How to Sort Array But Keep The Position of Duplicate Element in C?

Question

So, actually what I need is to keep the index of old array after sorted. So for example if I input [2,4,1,5,7,9,6] then the output is [2,0,1,3,6,4,5]. I already have use qsort and it works very well if there are no duplicate elements.

If there are duplicate elements, sometimes the first duplicate element was put last. For example, if the input is [5,4,6,5,2,1,3], what I want to be output is [5,4,6,1,0,3,2]. So, 5 which have index 0 put before 5 which have index 3. But, using qsort sometimes make the output [5,4,6,1,3,0,2].

Can you help me to fix this? Or should I create my own sorting function? Could you please help me to create it?

Here is my code:

#include <stdlib.h>

int* sortidx(double *X,int n)
{
    int *idx,i,j;

    int cmp(const void *a,const void *b)
    {
        return X[*(int*)a]>=X[*(int*)b]?1:-1;
    }

    idx=(int*)calloc(n,sizeof(int));

    for(i=0;i<n;i++)
    {
        idx[i]=i;
    }

    qsort(idx,n,sizeof(int),cmp);

    return idx;
}

Answer 1

You want one element to be considered greater than another if either its value is greater or if the values are equal and its index is greater. (This is the idea behind a stable sort algorithm.)

In this case, you know the indices of the elements being compared, so you can easily add that to your comparison criterion:

int cmp(const void *a, const void *b)
{
    return X[*(int*)a] > X[*(int*)b] ||
           (X[*(int*)a] == X[*(int*)b] && *(int*)a > *(int*)b)
           ?1:-1;
}

or, possibly more readably and pedantically correct (since it is not documented that a and b are guaranteed to be different):

int cmp(const void *a, const void *b)
{
    int idxa = *(const int*)a, idxb = *(const int*)b;
    if (X[idxa] > X[idxb]) return 1;
    if (X[idxa] < X[idxb]) return -1;
    return idxa - idxb;
}

The use of a nested function which refers to the argument X is a gcc extension, and may not work with other compilers. The Gnu implementation of the standard C library also contains the function qsort_r, which could be used to pass X to the comparison routine, but a more portable way to write the function would be to use an array of pointers rather than an array of indices:

int idxcmp(const void *a,const void *b)
{
    double *ap = *(double *const*)a, *bp = *(double *const*)b;
    if (*ap > *bp) return 1;
    if (*ap < *bp) return -1;
    return ap - bp; 
}

double** sortidx(double *X, size_t n)
{
    double **idx = calloc(n, sizeof(double*));
    for (size_t i=0; i<n; ++i) idx[i] = X + i;
    qsort(idx, n, sizeof(idx[0]), idxcmp);
    return idx;
}

(If you really want to return indices, you can convert the pointer to an index before returning.)

Answer 2

What you seek is a stable sorting algorithm. You can stabilize qsort in C, but it needs extra work. In C++ std::stable_sort exists.

If you need to stick to C, then you should implement your own stable sort. Here is a list of stable sorting algorithms:

B
Block sort
Bubble sort
Bucket sort
C
Cascade merge sort
Cocktail shaker sort
Counting sort
Cubesort
G
Gnome sort
I
Insertion sort
L
Library sort
M
Merge sort
O
Odd–even sort
Oscillating merge sort
P
Pigeonhole sort
Proxmap sort
R
Radix sort
T
Timsort