c - c の改良された qsort() 関数

Question

qsort() を使用して 1D 配列をソートするとします。ソートされた配列の要素から、ソートされる前に配列内でインデックス付けされたときにインデックス tis が持っていたインデックスを取得する簡単な方法はありますか。c[N] が d[N] としてソートされるとしましょう。整数 i、j から c[j]=d[i] を見つける方法は? 単純な方法を意味する場合、qsort (いくつかの追加パラメーターを使用) はこの種の情報 (並べ替え前と並べ替え後のインデックス間のバイジェクション) を格納しますか、またはこの種の情報を簡単に並べ替えて取得できる qsort の改善された関数が存在しますか?

Answer 1

初期配列に次のような構造を設定するとします。

struct IndexedInteger {
  int value;
  int index;
}

次に、ループでインデックスを埋める必要があります。

void addIndices(IndexedInteger * array, size_t num) {
  int i;
  for (i = 0; i < num; ++i) {
    array[i].index = i;
  }
}

次に、配列をソートします。

int compareIndexed(const void * elem1, const void * elem2) {
  IndexedInteger * i1, *i2;
  i1 = (IndexedInteger*)elem1;
  i2 = (IndexedInteger*)elem2;
  return i1->value - i2->value;
}

void sortArray(IndexedInteger * array, size_t num) {
  qsort(array, num, sizeof(IndexedInteger), compareIndexed);
}

次に、初期インデックスを使用して配列をソートします。

免責事項：私はこれを非常に速く書いているので、間違いがあるかもしれません.

Answer 2

できることはstruct、データ (この場合は整数) と、最初に配列にあった位置のインデックスに対応する整数を保持する を作成することです。明確にするために、

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

struct myData {
    int data;
    int orig_pos; // will hold the original position of data on your array
};

int myData_compare (const void* a, const void* b) {

    return ((struct myData*)a)->data - ((struct myData*)b)->data;
}

int main () {

    size_t N = 10; // size of your array
    struct myData* array = (struct myData*) malloc(N * sizeof(struct myData));
    for (size_t i = 0; i < N; i++) {
        array[i].data     = N - i; // array will hold 10,9,8,7,...1 in this order
        array[i].orig_pos = i;
    }
    qsort(array, N, sizeof(struct myData), &myData_compare);
    for (size_t i = 0; i < N; i++) {
        printf("\ndata: %d, orig_pos: %d", array[i].data, array[i].orig_pos);
    }
    return 0;
}