November 24th, 2009, 11:52 AM
[RESOLVED] Original indices before partial_sort()?
If I wanted to use partial_sort() to find the first k of n values (because of the O(n log k) complexity), is there any way to retrieve the original indices of the sorted vector? I need them to access other arrays that don't need to be sorted, but that share ordering.
For instance, I have a list of n x and y coordinates. If I sort them by x coordinate, that reorders the x vector. However, I need to do something like this (forgive the pseudocode):
for i = 1 to x.size()
plot x(i) and y(originalIndex(i))
in order to maintain the correct correspondence. This seems like a really common problem, but I can't find anything about it. I suppose I could just make a heap of the first k and push and pop, still making O(n log k), but that seems less...elegant.
Thanks for the help.
Last edited by fadecomic; November 24th, 2009 at 12:10 PM.
Reason: question resolved
Tags for this Thread
Click Here to Expand Forum to Full Width