CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Mar 2009
    Posts
    6

    [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 01:10 PM. Reason: question resolved

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    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 01:00 PM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Mar 2009
    Posts
    6

    Re: Original indices before partial_sort()?

    Head-smacker. Of course. You mean just write a comparison that really compares the x value, right? I hate not seeing the obvious ones.

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    Re: Original indices before partial_sort()?

    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5
    Join Date
    Mar 2009
    Posts
    6

    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
  •  





Click Here to Expand Forum to Full Width

Featured