Separate the even and odd places of the array in O (N) time and O (1) space

Question

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

We need to put all the elements of an odd place (1,3,5,7) together and even place the elements (2,4,6,8) together while maintaining order.

Input: [1,2,3,4,5,6,7,8]. Yield: [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]

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

My approach: 1. Split it like into (quick sort section) Problem: the order is not preserved. (1,7,3,5,4,6,2,8) -O (N) 2. Put the odd element in the right position and move all the other elements: Problem: for O (N) for each element, and the shift takes other O (N). So the time complexity becomes O (N ^ 2)

Is it possible that there is a complex solution O (N) and a complex solution O (1)?

Answer 1

See if you can generalize any of these loop-based permutation solutions, noting that the sorted indexes will 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, the end of the cycle. The problem here is that if n is not known in advance, then even if I [i] can be calculated "on the fly" (I [i] = (2 * i <n)? 2 * i: (2 * in) | 1; ), the problem is keeping track of which loops have already been processed, which may require O (n) space.

For 8 elements, these are two cycles, three 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, this is 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

27 3 , [1] (19 ), [3] (6 ) [9] (2 ).

Answer 2

.

:

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]

- ... , - .

, , :

, n n+1, n , .

[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 3

O(1) O(n).

, , - , . (IMHO) .

, O(logN) O(NlogN) " " ():

#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])

. . , - , , .

Answer 4

Here is a python program that works. No extra space required, just one pass through the array.
You do not require sorting numbers or saving the original order; just connect them.

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 result.

[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]