Jump to content

  • Log In with Google      Sign In   
  • Create Account

Sort and remap?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 sevenfold1   Members   -  Reputation: 133

Like
0Likes
Like

Posted 20 June 2011 - 12:27 PM

Is there a general C/C++ template or class I can use that can sort an array, but also return a remapping array?
(from old to new indices)

Thanks.

Sponsor:

#2 A Brain in a Vat   Members   -  Reputation: 313

Like
1Likes
Like

Posted 20 June 2011 - 12:32 PM

No, there's not.

This can be accomplished easily however. Rather than sorting the array itself, sort an array of indeces into that array. Your "remapping array" is then easily produced.

#3 sevenfold1   Members   -  Reputation: 133

Like
0Likes
Like

Posted 20 June 2011 - 12:43 PM

<br />No, there's not.<br /><br />This can be accomplished easily however.  Rather than sorting the array itself, sort an array of indeces into that array.  Your "remapping array" is then easily produced.<br />

&lt;br /&gt;&lt;br /&gt;&lt;br /&gt;<br /><br />
Thanks, that sounds like the best way to go about that.

But, wouldn't that just sort the array of indices?

Wouldn't I have to run sort twice, once to create the remapping, and again to sort the actual array?

#4 BitMaster   Crossbones+   -  Reputation: 4438

Like
1Likes
Like

Posted 20 June 2011 - 01:18 PM

Not tested but something like this should do the job:
template <typename T, typename Index = std::size_t>
class RemappingComparator
{
public:
   RemappingComparator(const std::vector<T>& refArray)
   :m_refArray(refArray)
   { }

   bool operator () (Index idx0, Index idx1) const
   {
      return m_refArray[idx0] < m_refArray[idx1];
   }

protected:
   const std::vector<T>& m_refArray;
};

// usage:
std::vector<RealType> realArray;
std::vector<std::size_t> remapArray;
// let the remapping array be filled with 0..(size-1)
std::sort(remapArray.begin(), remapArray.end(), RemappingComparator<RealType>(realArray));
Unfortunately, I don't have a compiler around to test it right now but it should be very close to the desired effect, although it could be made a bit nicer with some more work.

Wouldn't I have to run sort twice, once to create the remapping, and again to sort the actual array?

You would only have to run sort once. If you wanted to really sort the array (using the remapping array), you could do that in O(n) while sorting again would take O(n log(n)). For one array this is indeed more work (though not as much as sorting twice), but you wanted the remapping array.

Edit: need operator() for a functor, not operator <.

#5 iMalc   Crossbones+   -  Reputation: 2314

Like
0Likes
Like

Posted 20 June 2011 - 01:27 PM

So in other words, you want to sort the array but store enough information to essentially be able to put things back in the order they were, should you choose to do so?
You can do this by creating an ordered array of indicies and then sorting the main array and performing the swaps that occur during the sort, on both arrays.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#6 sevenfold1   Members   -  Reputation: 133

Like
0Likes
Like

Posted 20 June 2011 - 02:03 PM

<br />Not tested but something like this should do the job:<br />

<br />
template &lt;typename T, typename Index = std::size_t&gt;<br />
class RemappingComparator<br />
{<br />
public:<br />
   RemappingComparator(const std::vector&lt;T&gt;&amp; refArray)<br />
   :m_refArray(refArray)<br />
   { }<br />
<br />
   bool operator () (Index idx0, Index idx1) const<br />
   {<br />
      return m_refArray[idx0] &lt; m_refArray[idx1];<br />
   }<br />
<br />
protected:<br />
   const std::vector&lt;T&gt;&amp; m_refArray;<br />
};<br />
<br />
// usage:<br />
std::vector&lt;RealType&gt; realArray;<br />
std::vector&lt;std::size_t&gt; remapArray;<br />
// let the remapping array be filled with 0..(size-1)<br />
std::sort(remapArray.begin(), remapArray.end(), RemappingComparator&lt;RealType&gt;(realArray));<br />
<br />Unfortunately, I don't have a compiler around to test it right now but it should be very close to the desired effect, although it could be made a bit nicer with some more work.<br /><br />

Wouldn't I have to run sort twice, once to create the remapping, and again to sort the actual array?<br />

<br />You would only have to run sort once. If you wanted to really sort the array (using the remapping array), you could do that in O(n) while sorting again would take O(n log(n)). For one array this is indeed more work (though not as much as sorting twice), but you wanted the remapping array.<br /><br />Edit: need operator() for a functor, not operator &lt;.<br />

<br /><br /><br />


Just to clarify, the array of data needs to be sorted too.

I have other structures that index into this array of data, so I use the remapping array to fix them up
after the data is sorted.

So, as I see now, I can first sort an array of indices. Then use that to sort my array of data.
Then fixup my other structures.

Thanks for the help!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS