An improved qsort() function in c

Question

Suppose we are sorting a 1D array using qsort(), is there a simple way to retrieve from an element of the sorted array the index tis very element had when it was indexed in the array before it was sorted. Let's say c[N] become sorted as d[N], how to find from an integer i, j such that c[j]=d[i] ? When I mean a simple way, does qsort (with some additional parameter) stores this kind of information (bijection between indexations before an after sorting) or does it exist a qsort improved function that could sort and retrieve easily this kind of information ?

Answer 1

What you can do is create a struct which holds your data (in this case, an integer) and also an integer which corresponds to the index of the position where it was initially on your array. To clarify,

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

Answer 2

Assuming you populate the initial array with a structure like this:

struct IndexedInteger {
  int value;
  int index;
}

You would then need to fill the indices in a loop:

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

Then you will sort your array:

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

Then you will have your array sorted, with initial indices.

Disclaimer: I'm writing this quite fast, there might be mistakes.