""" Sort an array in wave form

Given an unsorted array of integers, sort the array into a wave like array.
An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..

Examples:

 Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
 Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
                 {20, 5, 10, 2, 80, 6, 100, 3} OR
                 any other array that is in wave form

 Input:  arr[] = {20, 10, 8, 6, 4, 2}
 Output: arr[] = {20, 8, 10, 4, 6, 2} OR
                 {10, 8, 20, 2, 6, 4} OR
                 any other array that is in wave form

 Input:  arr[] = {2, 4, 6, 8, 10, 20}
 Output: arr[] = {4, 2, 8, 6, 20, 10} OR
                 any other array that is in wave form

 Input:  arr[] = {3, 6, 5, 10, 7, 20}
 Output: arr[] = {6, 3, 10, 5, 20, 7} OR
                 any other array that is in wave form
"""

import random


def sortInWaveForm(nums):
    if len(nums) <= 1:
        return nums
    for i in range(0, len(nums), 2):
        if i + 2 < len(nums):
            a, b, c = nums[i], nums[i+1], nums[i+2]
            if a == max(a, b, c):
                nums[i], nums[i+1] = nums[i+1], nums[i]
            elif c == max(a, b, c):
                nums[i+1], nums[i+2] = nums[i+2], nums[i+1]
    if len(nums) % 2 == 0:
        if nums[-2] > nums[-1]:
            nums[-2], nums[-1] = nums[-1], nums[-2]
    return nums


test = [random.randint(-10, 10) for _ in range(10)]
print(test)
print(sortInWaveForm(test))
