Array index sorting

Question

I have an array that looks like this: a[]={2,3,4,5,8,2,5,6}.
Now I want to sort the indexes, but keep the original array and get something like this a_index[]={0,5,1,2,3,6,7,4}...

I have an algorithm O(N^2)for this. Can someone give me a better one (desirable O(NlogN))?

Answer 1

Create a structure containing two fields: indexand value.

Create an array of these structures, where each element (struct) is the source index and the value of the element in the array.

Sort the structure using ONLY the value in O (nlogn).

When you're done, iterate through the array in sorted order to get the sorted indexes.

Answer 2

qsort

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

int *TheArray;

int cmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    return (TheArray[ia] > TheArray[ib]) - (TheArray[ia] < TheArray[ib]);
}

int main(void) {
    int a[] = {2,3,4,5,8,2,5,6};
    size_t len = sizeof(a)/sizeof(*a);
    int a_index[len];
    int i;

    for(i = 0; i < len; ++i)
        a_index[i] = i;

    TheArray = a;
    qsort(a_index, len, sizeof(*a_index), cmp);

    for(i = 0; i < len; ++i)
        printf("%d ", a_index[i]);//5 0 1 2 6 3 7 4 : qsort is not a stable.
    printf("\n");

    return 0;
}

Answer 3

:

- : if (a[x] < a[x+1])

: if (a[a_index[x]] < a[a_index[x+1]])

And instead of: swap(a[x], a[x+1])

You will be doing: swap(a_index[x], a_index[x+1])

(where a_index is initialized to first contain the range of indices in sequential order (0..sizeof (a))

Since essentially a_index is just a lookup table, where the sorting value is the corresponding value in a. (In practice, this is just another level of indirection compared to what we usually do when we sort, since usually we will not directly compare (x) and (x + 1) either)

A similar solution can be made without doing in-place sorting if you are doing all your comparisons with the corresponding values ​​in a, instead of comparing