Wave Array

PROBLEM :

Given an array of integers, sort the array into a wave like array and return it.
In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

Example

Given [1, 2, 3, 4]

One possible answer : [2, 1, 4, 3]
Another possible answer : [4, 1, 3, 2]
 NOTE : If there are multiple answers possible, return the one thats lexicographically smallest.



Input:

The first line contains an integer T, depicting total number of test cases.
Then following T lines contains an integer N depicting the size of square matrix and next line followed by the value of array.


Output:

Print the array into wave like array.


Constraints:

1 = T = 30
1 = N = 100
0 = A[i] = 100

Example:

Input
1
5
5 7 3 2 8
Output
3 2 7 5 8

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

#include<iostream>
using namespace std;
void Wave_Array(int [],int ) ;
void bubble(int [],int ) ;

int main()
 {
int t,arr[100],no,i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   Wave_Array(arr,no) ;
 
   for(i=0;i<no;i++)
       cout<<arr[i]<<" " ;
 
   cout<<endl ;
}
return 0;
}

void Wave_Array(int arr[],int no)
{
    int i,temp;
   
    bubble(arr,no) ;
   
    for(i=0;i<no-1;i+=2)
    {
        temp=arr[i] ;
        arr[i]=arr[i+1] ;
        arr[i+1]=temp ;
    }
}

void bubble(int a[],int no)
{
    int i,j,temp ;
   
    for(i=0;i<no-1;i++)
    {
        for(j=0;j<no-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j] ;
                a[j]=a[j+1] ;
                a[j+1]=temp ;
            }
        }
    }
}

--------------------------------------------------------------------------------
ANOTHER c++ IMPLEMENTATION :(in O(n))
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
void Wave_Array(int [],int ) ;

int main()
 {
int t,arr[100],no,i ;
cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   Wave_Array(arr,no) ;
 
   for(i=0;i<no;i++)
       cout<<arr[i]<<" " ;
 
   cout<<endl ;
}
return 0;
}

void Wave_Array(int a[],int no)
{
    int i,temp ;
   
    for(i=0;i<no;i+=2)
    {
        if(i>0&&a[i]<a[i-1])
        {
            temp=a[i] ;
            a[i]=a[i-1] ;
            a[i-1]=temp ;
        }
       
        if(i<no-1&&a[i]<a[i+1])
        {
            temp=a[i] ;
            a[i]=a[i+1] ;
            a[i+1]=temp ;
        }
    }
}

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