編集 - 不必要なコンテキストの説明をすべて削除しました - 言葉が多すぎて、最終的に問題とは無関係です。要約すると、バランスの取れた KD ツリーを構築するプロセス中に座標の配列を分割しています (詳細については、ウィキペディアの記事、「構築」セクションを参照してください。実際には、それぞれが同じ比較によって分割されなければならない n 個の項目の k 個の並列配列があります)。
これは宿題ではありません。すべてのニュアンスが確実に伝わるように、質問を書きました。
並べ替えられた配列が与えられた場合:
int[] ints = { 0, 1, 2, 3, 4, 5, 6 };
//this one is important - my current solution fails on this
int[] ints2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Note due to a clarification asked by a colleague, all that's guaranteed about these arrays is that element[n] will be less than or equal to element[n+1].
Successful operations on these will separate them into two sub arrays L and R (indicated below):
/*ints == */ { 1, 3, 5, 0, 2, 4, 6 }
/*|> L <| |> R <|*/
/*ints2 == */ { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 }
/*|> L <| |> R <|*/
L contains the integers that are odd and R contains those that are even, whilst retaining the original sort-order of those elements within those subarrays.
The function will ideally NOT resort to re-sorting the elements (a lengthy sort operation will already have been performed in advance) and it won't use a temporary array. I believe that means I'm looking for O(N) complexity and O(1) memory.
The function can be provided with the start and end elements of each sub array - i.e. the caller can know in advance how many items will fall on the left/right sides (possibly by scanning the array in advance for odd/even). Edit in reality it starts off just as an array; so a solution that can work without these values is good, because otherwise the complete solution can only ever be at best O(2n) complexity in reality if an initial pass is required.
This where my current attempt is at now - I've updated it and commented it from what was in the original post.
public void DivideSubArray(int[] array, int leftStart, int leftCount,
int rightStart, int rightCount)
{
int currentLeft = leftStart, currentRight = rightStart;
int leftCounter = leftCount;
int temp;
int readahead;
while (leftCounter != 0) {
if ((array[currentLeft] % 2) == 0)
{
//remember the element we swap out
temp = array[currentRight];
//Set as next item on the right. We know this is the next lowest-sorted
//right-hand item because we are iterating through an already-sorted array
array[currentRight++] = array[currentLeft];
// * read ahead to see if there are any further elements to be placed
// * on the left - move them back one by one till there are no more.
readahead = currentLeft + 1;
while ((array[readahead] % 2) != 0)
{
array[currentLeft++] = array[readahead++];
leftCounter--;
}
//Now write the swapped-out item in, but don't increment our currentLeft.
//The next loop will check if the item is in the correct place.
array[currentLeft] = temp;
}
else //this item is already in the correct place
{
currentLeft++;
leftCounter--;
}
}
}
When called as follows:
int numOdd = ints.Count(i => (i % 2) == 1);
DivideSubArray(ints, 0, numOdd, numOdd, ints.Length - numOdd);
It produces the expected array for ints (and many other arrays), but not ints2:
{ 1, 5, 3, 7, 9, 0, 2, 6, 4, 8 }
So it partitions correctly - but swaps 3,5 and 6,4. I understand why: because in the first loop 5 is swapped to the left, then 2 is propagated over because the algorithm says that 5 is odd and should stay. I have a decision tree written out that'll fix it, but having followed it a few loops it infers that the solution is recursive.
I'm struggling to see how to get around this without running more sort operations within the sub array or creating temporary lists/arrays as workspace. Of course, though, a sort might increase complexity but keep the memory requirement; and if it turns out to be the fastest solution then it would make sense to use it.
You can see my current fastest (in run-time) and best memory solution under my answer. As a yardstick - the above attempt not only produces an incorrect result, but it also takes 3 times as long as the code in my answer.
I feel there must be a simple way to exploit a single 'spare' variable to swap the items - I just can't see it - I'm hoping the SO collective brain will :)
Of course, if the answer is 'no' then so be it.