CODEWITHSUNDEEP
carraysalgorithmsorting
user5082201
user5082201

Reputation:

Sort the index of an array

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 intact, and get something like this a_index[]={0,5,1,2,3,6,7,4}...

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

Upvotes: 6

Views: 1792

Answers (3)

amit
amit

Reputation: 178411

Create a struct that contains two fields: index and value.

Create an array of this structs, where each element (struct) is the original index and value of an element in the array.

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

When you are done - iterate the array in the sorted order to get the sorted indices.

Upvotes: 4

BLUEPIXY
BLUEPIXY

Reputation: 40145

use qsort E.g

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

Upvotes: 3

somaen
somaen

Reputation: 21

Wouldn't this essentially be solveable with an implementation of any sorting algorithm, with the following adjustment:

Where normally you would compare something like: if (a[x] < a[x+1])

You will now be doing: if (a[a_index[x]] < a[a_index[x+1]])

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

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

(Where a_index is initialized to contain the range of indexes in sequential order initially (0..sizeof(a))

Since essentially a_index is just a lookup-table, where the value for the purpose of sorting is the corresponding value in a. (In practice this is just another level of indirection compared to what we normally do when we sort, as normally we wouldn't compare (x) and (x+1) directly either)

A similar solution can be done without doing in-place sorting as well, as long as you perform all your comparisons against the corresponding values in a, instead of comparing the

Upvotes: 1

Related Questions