Quick partitioning of a sorted array into two sorted subarrays

Question

Edit - I deleted all the unnecessary contextual explanation - too verbose and ultimately unrelated to the problem. As a result, I split the coordinate arrays in the process of constructing a balanced KD tree ( see the Wikipedia article, “Building” section for more. K parallel arrays of n elements, each of which must be divided into the same comparison)

This is not homework. I wrote the question so that it conveys all the nuances.

Given the sorted arrays:

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 the explanation given by the colleague, all that is guaranteed for these arrays is that element[n] will be less than or equal to element[n+1] .

Successful operations on them will divide them into two auxiliary 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 integers that are odd, and R contains those that are even, while preserving the original sort order of these elements inside these subarrays.

Ideally, the function DOES NOT resort to re-sorting the elements (a lengthy sorting operation is already performed in advance), and it will not use a temporary array. I believe this means that I am looking for O (N) complexity and O (1) memory.

The function can be equipped with the initial and final elements of each auxiliary array - that is, the caller can know in advance how many objects will fall on the left / right side (perhaps by scanning the array in advance for the odd / even), Change , in fact, it starts as an array; therefore, a solution that can work without these values ​​is good, because otherwise a complete solution can only be, at best, O (2n) complexity in reality, if an initial pass is required.

This is where my current attempt is now - I updated it and commented on 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--; } } } 

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 breaks correctly - but the swaps are 3,5 and 6,4 . I understand why : because in the first cycle, 5 changes to the left, then 2 spreads, because the algorithm says that 5 is odd and should remain. I have a decision tree written that will fix it, but several cycles have followed that indicate that the solution is recursive.

I'm struggling to figure out how to get around this without having to do more sorting operations inside the auxiliary array or creating temporary lists / arrays as a workspace. Of course, however, sorting can increase complexity, but save the need for memory; and if that turns out to be the quickest solution, then it would be wise to use it.

In my answer you can see my fastest (at runtime) and best memory option. As a criterion - the above attempt not only leads to an incorrect result, but also takes 3 times as much code in my answer.

I believe that there should be an easy way to use one "spare" variable to replace elements - I just do not see it - I hope the collective brain of SO will be :)

Of course, if the answer is no, so be it.

Answer 1

I managed to get a solution together that didn't use a temporary array - it was incredibly slow for large N; I'm not even going to publish code for this, it was so bad!

Change - this is improved thanks to my original decision. The complexity is technically O (2n) (since the List.CopyTo method uses Array.Copy, which is O (n) according to the structure documentation), and the memory is O (n).

Yes, the solution simply takes an array and splits on the fly, rather than relying on knowing the odd / even division in advance. This means (when returning back to my actual code) that no initial pass is required - therefore it is preferable.

This solution is trivial: it scans the array, moving the odds back to the beginning of the array (or leaving them where they are, if they are already in the right place) and adds evens to the list. When the loop is complete, the list is copied to the rest of the array. It satisfies my requirement of complexity due to memory - in the worst case O (n) - and is a big improvement for the code I already used (it was twice as fast as the solution from two lists). It also does not require an initial pass to obtain an odd / even split.

 public void DivideSubArray(int[] array) { int currentOdd=0; List<int> even = new List<int>(array.Length / 2); for (int i = 0; i < array.Length; i++) { if ((array[i] % 2) != 0) { even.Add(array[i]); } else { if (currentOdd != i) array[currentOdd++] = array[i]; else currentOdd++; } } even.CopyTo(array, currentOdd); } 

Pay attention to the initial capacity of the list - as Mooing Duck mentions in the comments below, I may be able to further improve by using some probabilities and choosing a slightly higher value (provided that on average there will be approximately even division).

However, the algorithm works more slowly with even division - if there are more strange elements, then this is just a bunch of swaps. If there are more events, then yes, more Add operations are required, but it will only be a resize of the list, which will lead to reduced performance.

My last attempt is to see if I can achieve what izomorphius suggested is to plot the coefficients in the correct order and align in the reverse order or in any order without an additional array. If possible, then this solution will be O (1) memory, but O (n + (sorting complexity)) - and if the performance in practice is even half the speed, as above, I can go for it.

Answer 2

I think that you can make your task easier as follows: first change the array so that the odd numbers are first written at the beginning of the array in ascending order, and then the even numbers are written in descending order to the end. For your example, {0,1, ... 6} it will look like {1,3,5,6,4,2,0}. After that, make another linear pass to cancel the second part of the array (this is quite easy and straightforward).

Why do I think it should be easier? Good, because the thing you should do in the first step is what the regular qsort algorithm will do (with a slightly weird comparison operator). You can search the Internet to find out how the qsort section is executed (for example, here is an example here ). I sincerely believe that if you share your problem in these two steps, implementing the solution will be easier for you. Also note that the overall complexity does not change.

Hope this helps you.

EDIT: this is how I think you could do the first part of my sentence:

 public void DivideSubArray(int[] array, int leftStart, int leftCount, int rightStart, int rightCount) { int currentRight = rightStart + rightCount - 1; int current = leftStart; while (current < currentRight) { if ((array[current] % 2) == 0) { int temp = array[current]; array[current] = array[currentRight]; array[currentRight] = temp; currentRight--; } else { current++; } } } 

I do not provide code to cancel the even part, since I think this is pretty straightforward, and I also wanted to emphasize how this approach simplifies the code.

Answer 3

I don’t think there is any “direct” way to split the list without one end and the other to scramble, but there can still be a solution with constant space in linear time. The partitioning approach proposed by izomorphius will cause the right side of the end to be in reverse order (easily corrected in linear time) and the other end to be scrambled in a somewhat predictable form, with elements that came from the right side in the opposite order, with those that came to the left. For constant time, you can easily determine whether a given element has arrived on the right side (just compare it with the last element on the left), and then it can easily change the sequence of elements that were moved from right to left in linear time.

Once you have done this, you have a separation problem that is very similar to the original, but only half the size; the only difference is that the splitting criterion is based on whether the value of a node is greater or less than the "initial" last element, and not even or odd. Thus, you can significantly apply the original algorithm for a smaller data set. Since you can determine in advance which side of the split will have more objects, you can place the split so that the remaining side is no more than half the size of the original. The network effect is that splitting an array of size 2N takes O (1) times, while splitting an array of size N. Since a singleton array can be executed in constant time (which, obviously, this is possible), this means that splitting an array of arbitrary size consisting of two randomly mixed runs of sorted data into two disjoint runs of sorted data can be performed in linear time using constant space .

By the way, although this does not matter for integers, it is important to note that the above algorithm is based on the ability to compare two elements and know whether the first belongs to the left or right of the second. Therefore, it cannot be used as the basis for a stable sorting algorithm.

Answer 4

Can I try myself in this thread. I see you are talking about C #. I do not know the language, but I do not think that this is crucial for this task.

There is something missing in the description of the problem - where does the sorted array come from. I should probably write a comment asking for clarification, but I decided that I would go and write an answer that covers all the possibilities that I can think of. Hopefully this way the answer will serve more people in the future.

Basically, the as task puts us in the field: "You have an array, now it breaks in place." However, I would like to talk a little about the origin of this array:

• Case 1: An array is read from somewhere and sorted in code (in memory). If so, then splitting the Evens from the coefficients has an elegant solution that does not impose any overhead:
  • Determine the number of coefficients and coefficients (in one pass through the array O(n) ).
  • Determine the largest and smallest number in the array. Lets call them MAXM and MINM . This can be done in the first pass to determine an even and odd number.
  • Go through the array again, adding MAXM - MINM + 1 to each odd number. The goal is to make sure that all the odd numbers get bigger than the slope. It is linear in time O(n)
  • Split the array using the kth_element algorithm (basically, one pass of fast splitting). Separate the event from the strange, using the fact that you already know how many of them and that all the chances are the most. The algorithm works in linear time O(n) , but, unfortunately, I only have a link to the C ++ library implementation (no C #).
  • Go through all the slots of the array corresponding to the odd numbers, and subtract MAXM - MINM + 1 from each number to get the original odd numbers. It is also linear in time O(n)
  • Finally, sort the Evens and Odds separately. This will not increase the complexity of sorting in general, but you will have parts separated from each other.
• Case 2:. You are reading an array that is already sorted from some permanent storage, say, a file on your hard drive and you know in advance the number of coefficients and coefficients.
  • In this case, you just need to have a place in the array on which you enter the numbers: one for the next to follow the even number, and one for the next following the odd number. This solution should be obvious, and it does not affect performance at all.
• Case 3:. You are reading an array already sorted from some permanent storage, say, a file on your hard drive, but you DO NOT know the number of coefficients and coefficients in advance.
  • Start filling up the evens from the beginning of the array and the coefficients from the end of the array. Thus, at the end, two sequences will meet in the middle.
  • Thus, you will have a split of the Evens, and the odd numbers will decrease, not increase. You just go and do the inverse of the odd part (which is also linear) in place, and you have the array you need.

We hope that at least one of the scenarios described will allow you to solve the problem using this idea.

Answer 5

I think maybe O (n) time and O (1) spatial algorithm. But it can be too hard to understand.

I will run you away from this:

• shows you a special case of the original problem, we call it A.
• Consider the inverse problem A, we call it problem B. And we show that if we get O (n) time and O (1) a spatial solution for any of them, then we can change it to solve another problem.
• I will show you that problem B can be solved in O (n) time and O (1) space, but the solution is quite complicated and requires a lot of math.

Thus, this is unlikely to help you solve your problem easily, otherwise we can easily solve problem B.

1. Consider a special case:

Let A [] = {1,2,3,4,5,6,7,8}, from 1 to 2n and n = 4 in this example. So you want to change it to {1,3,5,7,2,4,6,8}, right? We call this problem A. In general, this means that you have an array A of size 2n, from A [1] to A [2n], you want to change it to A [1], A [3], A [5 ] ..., A [2n-1], A [2], A [4], A [6], A [2n]. This is a special case of your problem. If you get a solution for your problem, then it will be easy to solve problem A.

2. The reverse of problem A.

Consider a related problem. Let B = {1,2,3,4,5,6,7,8}, and we want to change it to {1,5,2,6,3,7,4,8}. This is the same as you have a deck of cards, and you want to make the perfect shuffle that divides them into 2 equal parts and combines them as an alternative. So, you have an array B of size 2n, from B [1] to B [2n]. You want to change it to B [1], B [n + 1], B [2], B [n + 2], .... B [n], B [2n].

Then you will understand that problem A and problem B are inverse operations. That is, for an array of size 2n, if you do it using operation B, and then do it using operation A, then it will become the original array, and it will be the same if we first B and then A.

If you have some information about the permutation, you will find out that if we get an algorithm for A, then we can change it to work for B. If you are not familiar with this, I can go into more detail below.

3. Problem B is not easy to solve.

Is there such an O (n) time and O (1) spatial algorithm for Problem B. He does this, you can look it at Calculating Loops in Perfect Shuffle Permutation . This is a 12-page document that means you are unlikely to come up with this solution in an interview. I read it, and he really needs a lot of math in number theory. And this is more of a theoretical solution.

Conclusion:

It seems that there is no simple (which means that 10-page paper is not required) O (n) time O (1) a spatial solution to your problem, even for a special case in problem A. Otherwise, we can change it to solve problem B. I'm not sure if there is a solution O (n) of time O (1) in your generalized problem.

If you are really interested in this problem. You can look at Knuth Art of Computer Programming. The chapter discusses the In Situ permutation.

It may not be easy to understand my idea, so if you have any questions, please comment.

Answer 6

 // stable_partition.cpp // example general inplace stable partition. #include <algorithm> #include <functional> #include <iterator> #include <iostream> #include <vector> template<typename Fwd, typename Pred> Fwd inplace_stable_partition(Fwd first, Fwd last, Pred pred) { ptrdiff_t nmemb = std::distance(first, last); if (nmemb == 1) return pred(*first) ? last : first; if (nmemb != 0) { Fwd split = first; std::advance(split, nmemb/2); first = inplace_stable_partition(first, split, pred); last = inplace_stable_partition(split, last, pred); std::rotate(first, split, last); std::advance(first, std::distance(split, last)); } return first; } int main(int argc, char* argv[]) { using namespace std; vector<int> iv; for ( int i = 0; i < 10; i++ ) iv.push_back(i); copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " ")); cout << endl; inplace_stable_partition(iv.begin(), iv.end(), bind2nd(modulus<int>(), 2)); copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " ")); cout << endl; return 0; } 

Answer 7

It looks like you are looking for a stable in-place sorting algorithm with a special relational order of elements (any odd number is less than any even number).

Given this, I think you cannot be better than O (n ln n).

I would go to sort the merger in place.

If you don’t need to keep the order of elements with the same value, go for quick sorting, which is much easier to process in place (however, with billions of elements, this may not be very good).