Before going for what is the problem let’s first understand few terms we are about to do in this post.

What does it mean by “wave array”

Well, you have seen waves right? how do they look? if you will form a graph of them it would be some in some up-down fashion. that is what you have to do here, you are supposed to arrange numbers in such a way that if we will form a graph it will be in an up-down fashion rather than a straight line.

Problem

Given an unsorted array of integers, sort the array into a wave 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[] = {5, 10, 1, 12, 45, 17, 89, 63}
Output: arr[] = {10 1 12 5 45 17 89 63} 

Input: arr[] = {10, 23, 54, 7, 4, 9, 53, 12}
Output: arr[] = {23 10 54 4 9 7 53 12}

Explanation

here you can see {10, 5, 6, 2, 20, 3, 100, 80} first element is larger than the second and the same thing is repeated again and again. large element – small element-large element -small element and so on .it can be small element-larger element – small element-large element -small element too. all you need to maintain is the up-down fashion which represents a wave. there can be multiple answers.

Optimized approach for wave 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. 

Follow the steps mentioned below to implement the idea:

• Traverse all even positioned elements of the input array, and do the following.
  • If the current element is smaller than the previous odd element, swap the previous and current.
  • If the current element is smaller than the next odd element, swap next and current.

Solution

Below is the solution of this problem in golang.

package main

import (
    "fmt"
    _ "sort"
)

// sorting array in wave for which is
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] 
// and so on till array is sorted.
func sortInWaveForm(arr []int) {
    // Traverse all even elements
    for i := 0; i < len(arr)-1; i += 2 {
        // If current even element is smaller than previous
        if i > 0 && arr[i-1] > arr[i] {
            arr[i], arr[i-1] = arr[i-1], arr[i]
        }
        // If current even element is smaller than next
        if i < len(arr)-1 && arr[i] < arr[i+1] {
            arr[i], arr[i+1] = arr[i+1], arr[i]
        }
    }
}

func main() {
    // 5, 10, 1, 12, 45, 17, 89, 63
    // 10,23,54,7,4,9,53,12
    arr := []int{10, 23, 54, 7, 4, 9, 53, 12}
    fmt.Println("Before Tsunami Waves", arr)
    sortInWaveForm(arr)
    fmt.Println("After Tsunami Waves", arr)
}

Output:

Before Tsunami Waves [10 23 54 7 4 9 53 12]
After Tsunami Waves [23 10 54 4 9 7 53 12]

Time Complexity: O(N)
Auxiliary Space: O(1)

Leave a comment if want another approach to solve this problem or want solution in other programming languages as well, you can comment your code as well if you want your code on my website then please do comment.

Thanks for reading 🙂