How to sort an array, but keep the position of the duplicate element in C?

Question

So actually I need to keep the index of the old array after sorting. So, for example, if I enter [2,4,1,5,7,9,6], then there will be a way out [2,0,1,3,6,4,5]. I already have qsortit and it works very well if there are no duplicate elements.

If there are repeating elements, sometimes the first repeating element was placed last. For example, if the input is [5,4,6,5,2,1,3]what I want to deduce [5,4,6,1,0,3,2]. So, 5those that have an index 0are placed in front of 5that have an index 3. But using qsort, sometimes we conclude [5,4,6,1,3,0,2].

Can you help me fix this? Or should I create my own sort function? Could you help me 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 larger than the other if either its value is greater or if the values ​​are equal and its index is greater. (This is the idea of ​​a stable sorting algorithm.)

In this case, you know the performance of the items being compared, so you can easily add this to your comparison criteria:

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 perhaps, more readable and meticulously correct (since no documented that aand bare guaranteed to differ):

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

, X, gcc . Gnu C qsort_r, X , , :

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

( , .)

Answer 2

, , . qsort C, . ++ std::stable_sort .

C, . :

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