Segregate even and odd places of an array in O(N) time and O(1) space

Question

Given an array a = {1,2,3,4,5,6,7,8}

We should bring all the odd place elements(1,3,5,7) together and even place elements(2,4,6,8) together while preserving the order.

Input : [1,2,3,4,5,6,7,8]. Output : [1,3,5,7,2,4,6,8].

Update:(Example 2) Example 2 : [3,54,77,86,45,2,25,100] Output : [3, 77, 45, 25, 54, 86, 2, 100]

Restrictions: O(N) time complexity and O(1) space complexity.

My approach : 1. partitioning it like in (quicksort partition) Problem : the order is not preserved. ( 1,7,3,5,4,6,2,8) -O(N) time complex 2. Putting the odd element to the rightful position and shifting all the other elements : Problem : It comes to O(N) for each element and shifting takes another O(N). So the time complexity becomes O(N^2)

Is there a O(N) time complex and O(1) space complex solution possible?

Answer 1

The problem seems rather hard with O(1) and O(n) restrictions.

Best match I can find is an article Stable minimum space partitioning in linear time, where they propose a solution for slightly more general problem. However, their algorithm is complex and (IMHO) not applicable in practice.

Unless it is a theoretical question, I suggest to relax restrictions to O(logN) and O(NlogN) respectively, and use simple 'stable partitioning' algorithm (updated):

#inplace reverse block [begin,end) in list l
#O(|end-begin|)
def reverse(l, begin, end):
    p = begin
    q = end - 1
    while p < q:
        l[p], l[q] = l[q], l[p]
        p = p + 1
        q = q - 1

#inplace swaps blocks [begin, mid) and [mid, end) and
#returns a new pivot (dividing point)
#O(|end-begin|)
def swap(l, begin, mid, end):
    reverse(l, begin, mid)
    reverse(l, mid, end)
    reverse(l, begin, end)
    return (end - (mid - begin))

#recursive partitioning: partition block [begin, end) into
#even and odd blocks, returns pivot (dividing point)
##O(|end-begin|*log|end-begin|)
def partition(l, begin, end):
    if end - begin > 1:
        mid = (begin + end) / 2
        p = partition(l, begin, mid)
        q = partition(l, mid, end)
        mid = swap(l, p, mid, q)
        return mid
    return begin if l[begin] % 2 == 0 else begin + 1

def sort(l):
    partition(l, 0, len(l))
    return l

print sort([1,2,3,4,5,6,7,8])

Update. For an updated question, article is a direct match. So unless there is some trick which abuses the numerical nature of elements, we don't have a simple solution to that problem.

Answer 2

See if you can generalize either of these permutation solutions based on cycles, noting that sorted indices would be I[] = {0,2,4,6,1,3,5,7}, I[1] = 2, I[2] = 4, I[4] = 1 , end of cycle. I[3] = 6, I[6] = 5, I[5] = 3, end of cycle. The issue here is if n is not known in advance, then even though I[i] can be calculated on the fly (I[i] = (2*i < n) ? 2*i : (2*i-n) | 1; ), the issue is keeping track of which cycles have already been processed, which could require O(n) space.

For 8 elements, it's two cycles, 3 elements each:

             0 1 2 3 4 5 6 7
       I[] = 0 2 4 6 1 3 5 7

   t = a[1]  2
a[1] = a[2]  1 3 3 4 5 6 7 8 
a[2] = a[4]  1 3 5 4 5 6 7 8
a[4] = t     1 3 5 4 2 6 7 8
   t = a[3]  4
a[3] = a[6]  1 3 5 7 2 6 7 8
a[6] = a[5]  1 3 5 7 2 6 6 8
a[5] = t     1 3 5 7 2 4 6 8

for 12 elements, it's just one cycle of 10 elements

               0  1  2  3  4  5  6  7  8  9 10 11  
         I[] = 0  2  4  6  8 10  1  3  5  7  9 11

    t = a[ 1]  2
a[ 1] = a[ 2]  1  3  3  4  5  6  7  8  9 10 11 12
a[ 2] = a[ 4]  1  3  5  4  5  6  7  8  9 10 11 12
a[ 4] = a[ 8]  1  3  5  4  9  6  7  8  9 10 11 12
a[ 8] = a[ 5]  1  3  5  4  9  6  7  8  6 10 11 12
a[ 5] = a[10]  1  3  5  4  9 11  7  8  6 10 11 12
a[10] = a[ 9]  1  3  5  4  9 11  7  8  6 10 10 12
a[ 9] = a[ 7]  1  3  5  4  9 11  7  8  6  8 10 12
a[ 7] = a[ 3]  1  3  5  4  9 11  7  4  6  8 10 12
a[ 3] = a[ 6]  1  3  5  7  9 11  7  4  6  8 10 12
a[ 6] = t      1  3  5  7  9 11  2  4  6  8 10 12

For 27 elements, it's 3 cycles, starting at a[1] (19 elements), a[3] (6 elements), and a[9] (2 elements).

Answer 3

This is a partial answer only.

Here's the executable pseudocode for the first half of the array:

def magic_swap(arr):
    mid = len(arr) / 2 + (1 if len(arr) % 2 == 1 else 0)

    for i in range(1, mid):
        arr[i], arr[i*2] = arr[i*2], arr[i]

The second half is the tricky part... I will update this answer if I ever figure out it.

For people who want to figure this out, here's the results for the first few array sizes:

Note that arrays of size n and n+1, when n is odd, always have the same sequence of swaps in this approach.

[1, 2]
[1, 3, 2]
[1, 3, 2, 4]
[1, 3, 5, 4, 2]
[1, 3, 5, 4, 2, 6]
[1, 3, 5, 7, 2, 6, 4]
[1, 3, 5, 7, 2, 6, 4, 8]
[1, 3, 5, 7, 9, 6, 4, 8, 2]
[1, 3, 5, 7, 9, 6, 4, 8, 2, 10]
[1, 3, 5, 7, 9, 11, 4, 8, 2, 10, 6]
[1, 3, 5, 7, 9, 11, 4, 8, 2, 10, 6, 12]
[1, 3, 5, 7, 9, 11, 13, 8, 2, 10, 6, 12, 4]
[1, 3, 5, 7, 9, 11, 13, 8, 2, 10, 6, 12, 4, 14]
[1, 3, 5, 7, 9, 11, 13, 15, 2, 10, 6, 12, 4, 14, 8]
[1, 3, 5, 7, 9, 11, 13, 15, 2, 10, 6, 12, 4, 14, 8, 16]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 10, 6, 12, 4, 14, 8, 16, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 10, 6, 12, 4, 14, 8, 16, 2, 18]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 6, 12, 4, 14, 8, 16, 2, 18, 10]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 6, 12, 4, 14, 8, 16, 2, 18, 10, 20]

Answer 4

Here is a python program that works. No extra space needed, only one pass through the array.
You don't require the numbers to be sorted or to keep the original order; just put them together.

arr = [1,3,2,4,5,6,3,55,66,77,21,4,5]
iFirst = 0
iLast  = len(arr)-1
print arr
while (iFirst < iLast):
    while ((arr[iFirst] & 1)==1):  # find next even at the front
        iFirst += 1
    while ((arr[iLast] & 1)==0):   # find next odd at the back
        iLast -= 1
    k = arr[iLast]                 # exchange them
    arr[iLast] = arr[iFirst]
    arr[iFirst] = k
    iFirst += 1
    iLast -= 1
print arr  

Here is the output.

[1, 3, 2, 4, 5, 6, 3, 55, 66, 77, 21, 4, 5]
[1, 3, 5, 21, 5, 77, 3, 66, 55, 6, 4, 4, 2]