Sort Array in Wave Form

November 6, 2021

Sort Array in Wave Form

In sort array in wave form we have to sort the array such that the elements are arranged in a wave. It is a famous interview problem that is asked in many technical interviews. In this article, we will provide a C++ solution with an explanation.

Sort Array in Wave Form Problem Description

Sort Array in Wave Form Problem Description

Given an array of n integers. Sort the array in such a way that the numbers in the array are arranged in a waveform from left to right.

Example –

3 2 4 1 is a wave

But 1 2 3 is not a wave.

Input:

  • First line contains single integer n – the size of the array.
  • Next Line contains n integers the elements of the array.

Output:

  • N integers sorted in waveform.

Sort Array in Wave Form Problem Solution

Naive Approach

In this approach, we will first sort the elements of the array in increasing order. Since the array elements are in increasing order swapping adjacent elements starting from the first elements will result in the arrangement of numbers in wave form.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
void waveSort(int arr[], int n)
{
    sort(arr, arr + n);

    for (int i = 0; i < n – 1; i += 2)
        swap(arr[i], arr[i + 1]);
}
int main()
{
    int n = 5;
    int arr[5] = {3, 4, 2, 1, 5};
    waveSort(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << ” “;
    return 0;
}

Output

2 1 4 3 5

Optimized Approach

Note that we don’t have to achieve a particular configuration of numbers. We only have to output the numbers in a wave form.

To achieve this we can fix even positions of the array to have integers greater than both the adjacent positions. This can be done via a single loop & checking each even positioned element only.

Time Complexity – O(n)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
void waveSort(int arr[], int n)
{
    // Check All Even ELements

    for (int i = 0; i < n; i += 2)
    {
        if (i > 0 && arr[i – 1] > arr[i])
            swap(arr[i], arr[i – 1]);
        if (i < n – 1 && arr[i + 1] > arr[i])
            swap(arr[i], arr[i + 1]);
    }
}
int main()
{
    int n = 5;
    int arr[5] = {3, 4, 2, 1, 5};
    waveSort(arr, n);

    for (int i = 0; i < n; i++)
        cout << arr[i] << ” “;
    return 0;
}

Output

4 2 3 1 5

2 comments on “Sort Array in Wave Form”