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