Convert array into Zig-Zag fashion

PROBLEM :
Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. 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.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the size of array.
The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.

Output:
Print the array in Zig-Zag fashion.

Constraints:
1 = T = 100
1 = N = 100
0 =A[i]<=10000

Example:
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

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#define max 100
void Zigout_Zag_fashion(int [],int ) ;
int main()
 {
int t,no,i ;
int arr[max] ;
cin>>t ;
    while(t--)
    {
        cin>>no ;
        for(i=0;i<no;i++)
            cin>>arr[i] ;
       
         Zigout_Zag_fashion(arr,no) ;
       
         for(i=0;i<no;i++)
            cout<<arr[i]<<" " ;
         cout<<endl ;
    }
return 0;
}

void Zigout_Zag_fashion(int arr[],int no)
{
    int i,temp ;
    for(i=0;i<no-1;i++)
    {
        if(i%2==0)
        {
            if(arr[i]>arr[i+1])
            {
                temp=arr[i] ;
                arr[i]=arr[i+1] ;
                arr[i+1]=temp ;
            }
        }
        else
        {
            if(arr[i]<arr[i+1])
            {
                temp=arr[i] ;
                arr[i]=arr[i+1] ;
                arr[i+1]=temp  ;
            }
        }
    }
}

---------------------------------------------------------------------------------