Convert array into Zig-Zag fashion

Last updated: 29th Aug, 2020

Problem Statment

Given an array A (distinct elements) of size N. Rearrange the elements of array in zig-zag fashion. The converted array should be in form a < b > c < d > e < f. The relative order of elements is same in the output i.e you have to iterate on the original array only.

Example 1:

Input
2
7
4 3 7 8 6 2 1
4
1 4 3 2
Output:
3 7 4 8 2 6 1
1 4 2 3

Method:

Basic idea is to swap the elements.
Check if the element is even.
If the even element is zero and greater then odd element
Then Swap the elements

Python Code


  
t=int(input())
for k in range(t):
    n=int(input())
    a = list(map(int, input().split()))
                            
    i = 0
                            
    x = len(a)
                            
    if(x % 2 != 0):
        for i in range(0, x-2, i+2):
            if((a[i] > a[i+1] or a[i+2] > a[i+1])):
                if(a[i] > a[i+1]):
                    temp = a[i+1]
                    a[i+1] = a[i]
                    a[i] = temp
                if(a[i+2] > a[i+1]):
                    answer = a[i+2]
                    a[i+2] = a[i+1]
                    a[i+1] = answer
            else:
                for i in range(0, x-3, i+2):
                    if((a[i] > a[i+1] or a[i+2] > a[i+1])):
                        if(a[i] > a[i+1]):
                            temp = a[i+1]
                            a[i+1] = a[i]
                            a[i] = temp
                        if(a[i+2] > a[i+1]):
                            answer = a[i+2]
                            a[i+2] = a[i+1]
                            a[i+1] = answer
                if(a[-1] < a[-2]):
                    answer = a[-1]
                    a[-1] = a[-2]
                    a[-2] = answer
            print(*a)