Wiggle Sort

'''
This can be done in O(n) time by doing a single traversal of the given array. The idea is based on the fact that if we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd elements, we don't need to worry about oddly positioned elements.

The following are simple steps.
1) Traverse all even positioned elements of the input array, and do the following.
....a) If the current element is smaller than the previous odd element, swap previous and current.
....b) If the current element is smaller than the next odd element, swap next and current.
'''
class Solution:
    #Complete this function
    #Function to sort the array into a wave-like array.
    def convertToWave(self,arr,N):
        for i in range(0,N,2):
            if i-1>=0:
                if arr[i-1]>arr[i]:
                    arr[i-1],arr[i]=arr[i],arr[i-1]
            if i+1<=N-1:
                if arr[i]<arr[i+1]:
                    arr[i],arr[i+1]=arr[i+1],arr[i]
        return arr