Algorithm question: in-place multi-bringToFront?

[mw]

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.

If you don’t care the remaining elements’ order, just swap the 
head N elements with the index array’s pointing to. (unstable 
swap, linear to N=index.length)

If you need to keep them still in the original order, first grab 
those indexed elements and mark their place as holes, then scan 
from arr[max(index)] backwards to arr[0] move the un-indexed 
elements to fill those holes, finally set the head elements with 
the indexed elements. (stable move, linear to max(index))