
November 24th, 2009, 11:52 AM
#1
[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):
partial_sort(x);
for i = 1 to x.size()
plot x(i) and y(originalIndex(i))
end
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

November 24th, 2009, 11:57 AM
#2
Re: Original indices before partial_sort()?
One way is to create a vector of indices, pointers or iterators, then sort that based on the original vector's elements.
By the way, if you only want to find the first k of n values, then you should use std::nth_element, not std::partial_sort.
Last edited by laserlight; November 24th, 2009 at 12:00 PM.

November 24th, 2009, 12:01 PM
#3
Re: Original indices before partial_sort()?
Headsmacker. Of course. You mean just write a comparison that really compares the x value, right? I hate not seeing the obvious ones.

November 24th, 2009, 12:04 PM
#4
Re: Original indices before partial_sort()?
Originally Posted by fadecomic
You mean just write a comparison that really compares the x value, right?
Yes, it will compare based only on the x value of the elements of the original vector.

November 24th, 2009, 12:08 PM
#5
Re: Original indices before partial_sort()?
Thanks for the tip on nth_element. That clearly involves less work. That will at best be O(n) I see.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
