Algorithm question: in-place multi-bringToFront?

[wjoe]

On Thursday, 28 May 2020 at 23:47:50 UTC, H. S. Teoh wrote:
> Just pickin' yall's smart brains:
>
> Given an array A and a set of indices into the array, is there 
> a fast algorithm for rearranging A in-place so that the 
> elements at the given indices are moved to the front?
>
> E.g.: A = [ 0, 1, 2, 3, 4, 5 ], index = [ 1, 3, 5 ]
>
> The result should have 1, 3, and 5 at the front of the array 
> (the exact
> order is unimportant).
>
> For efficiency considerations, assume the size of the index is 
> relatively small, but the array itself may be quite large, so 
> scanning the entire array or copying large chunks of it is 
> undesirable.
>
>
> T

I would just sort index[], to have more cache-friendly access to 
A[], and then swap the elements in order, e.g. pseudo-code:

foreach (i, ref i_index; index.sort)
{
   swap(A[i], A[i_index]);
   i_index = i; // if necessary; update the index in the index 
array
}