Wave Array

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]

Now, according to our problem we have to sort the array in a way that is satisfies the required pattern.

If we closely look at the pattern then we find that element at odd index is less then it's left and right element (provided both exist) and element at even is greater then it's neighbours.

So, if in a sorted array we take pair of two elements and swap them, traversing the whole array in this manner will give us the wave array at the end.

Thus, time complexity of the solution will be O(n).

STEPS

Sort the array.
Starting at index = 0 to index < n, swap elements.
index += 2.
The array is now sorted in wave like fashion.

CODE in Java

public ArrayList<Integer> wave(ArrayList<Integer> a) {

     Collections.sort(a);

     for(int i=0;i<a.size()-1;i++)

     {

         int t = a.get(i);

         a.set(i,a.get(i+1));

         a.set(i+1,t);

         i++;

     }

     return a;



 }