**0**

# Sort and remap?

###
#3
Members - Reputation: **123**

Posted 20 June 2011 - 12:43 PM

<br /><br /><br /><br /><br /><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 &quot;remapping array&quot; is then easily produced.<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
Crossbones+ - Reputation: **3765**

Posted 20 June 2011 - 01:18 PM

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.

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.Wouldn't I have to run sort twice, once to create the remapping, and again to sort the actual array?

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

###
#5
Crossbones+ - Reputation: **2287**

Posted 20 June 2011 - 01:27 PM

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.

My website dedicated to sorting algorithms

###
#6
Members - Reputation: **123**

Posted 20 June 2011 - 02:03 PM

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

<br /> template <typename T, typename Index = std::size_t><br /> class RemappingComparator<br /> {<br /> public:<br /> RemappingComparator(const std::vector<T>& refArray)<br /> :m_refArray(refArray)<br /> { }<br /> <br /> bool operator () (Index idx0, Index idx1) const<br /> {<br /> return m_refArray[idx0] < m_refArray[idx1];<br /> }<br /> <br /> protected:<br /> const std::vector<T>& m_refArray;<br /> };<br /> <br /> // usage:<br /> std::vector<RealType> realArray;<br /> std::vector<std::size_t> remapArray;<br /> // let the remapping array be filled with 0..(size-1)<br /> std::sort(remapArray.begin(), remapArray.end(), RemappingComparator<RealType>(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 /><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 <.<br />Wouldn't I have to run sort twice, once to create the remapping, and again to sort the actual array?<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!