Best way to maintain original indexes after sorting

general
,
1

Lets say i have 10 numbers (unsorted)

29,5,23,4,56,21,66,8,43,9

Once i sort them, their indices are changed.

4,5,8,9,21,23,29,43,56,66

I have an index to an element in the unsorted array. Now i want to know which position the same element is in the sorted array. For example, i have the index 6. In the sorted array, it points to the number 66. In the unsorted array, the same element is at index 9.

Is there a way i can find out the index in the second array, in constant time?

I figured read the element at the given index, then apply a binary search in the sorted array to get a O( log(n) ) worst time complexity.

Generating a hash table would require n*log(n) time as well.

I was just wondering if there was a way to sort the elements and store the locations both in one go, so it would take only n*log(n) time, opposed to 2*n*log(n) time if we do sort and generating the hash table.

Or if there is some predefined function/container/library in c++ that can be used to accomplish what im trying to do.

2

i known why this question is being asked :stuck_out_tongue:

11 Likes
3

you can keep a structure of elements having value and original indices and then qsort it wrt the elements.
O(nlog n) but very easy to access

1 Like
4

for(i=0;i<n;i++)
{
scanf("%d",&a[i].first);
a[i].second=i;
}
sort(a,a+n);
for(i=0;i<n;i++)
{A[a[i].second]=i;
}
i would have done this
binary as well as hash table would take O(n*log(n)) this would take O(n) :slight_smile: i used pair which is part of STL

3 Likes
5

Then keep it to yourself :stuck_out_tongue:

Seriously.

6

But to figure out what was the element at the index 5 of the unsorted array, i’d have to look through the entire sorted array and compare the value of the original index in the structure with the one i’m looking for.

O(n) complexity i think.

7

Ah! great. Now instead of nlog(n) for generating hash table, it only takes O(n) time.

8

is it right to sort pair using sort() fuction???

9

@raja44ever Yes. See: http://discuss.codechef.com/questions/42473/how-to-sort-the-co-ordinates-x-y-with-respect-to-x-c-stl

10

You can overload the compare function in STL sort like

int arr[MAX};//your array
int index[MAX];//array that contains sorted indexes
//use sort(index,index+n) to sort
bool cmp(int a,int b)
{
    return arr[a]<arr[b];

}
1 Like