どのように配列を並べ替えるが、重複要素の位置をCに保持するか？

Question

実際には、ソート後に古い配列のインデックスを保持する必要があります。たとえば、入力した場合、[2,4,1,5,7,9,6]、出力は[2,0,1,3,6,4,5]です。私はすでにqsortを使用しており、重複する要素がなければうまく動作します。

重複する要素がある場合は、最初に重複する要素が最後に配置されることがあります。たとえば、入力が[5,4,6,5,2,1,3]の場合、出力する出力は[5,4,6,1,0,3,2]です。従って5のインデックス0は、3の5の前に置かれています。しかし、qsortを使用すると出力が[5,4,6,1,3,0,2]になることがあります。

この問題を解決するお手伝いをしてもらえますか？または私自身のソート機能を作成する必要がありますか？あなたはそれを作成するために私を助けてくれますか？

#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

あなたは、その値が大きいのいずれか場合または値が等しく、その指数が大きい場合は、1つの要素が他よりも大きいと見なされたいです。 （これは安定ソートアルゴリズムの背後にある考え方である）

この場合は、あなたが簡単に比較基準にそれを追加することができますので、あなたは、比較されている要素のインデックスを知っている：

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

または、おそらくより読み出し可能とpedantically正しい（aとbが異なることが保証されることが立証されていないため）：

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 EXTあります他のコンパイラでは動作しない可能性があります。標準CライブラリのGnuの実装には、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

何を求めることはstable sorting algorithmです：

は、ここに私のコードです。あなたはCでstabilize qsortをすることができますが、余分な作業が必要です。 C++ではstd::stable_sortが存在します。

Cに固執する必要がある場合は、独自の安定した並べ替えを実装する必要があります。ここでは、安定ソートアルゴリズムのlist次のとおりです。

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