Sort an array in wave-form ( Wave Sort ) in C++

In this tutorial, we are going to learn how to sort an array in wave-form in C++ which is also known as wave sort. The basic approach will be to sort an array and then print last and first array element simultaneously to create a wave-like structure but this will take O(n* log n)  time as sorting of the array will take this much time. So we will try to solve this problem using a different approach.

We will try to solve this problem in linear time. We will traverse the array from index 1 and each time we will check the previous number and next number if that number will be greater to the current number we will replace it with the current number.

Example:

Consider an array of length 5.




Let array elements be: 1, 2, 3 , 4 , 5

At index=1:

Here 2 is greater than 1 we will swap them. Now array will become 2->1->3->4->5

We will check if 3 is greater than 1, if not then it will remain unchanged. Now we will increment index by 2 and follow the same procedure until we reach index=n-2.

At last, we will get an array like this:    2->1->4->3->5, which is in the waveform.

2      4      5
  \   /  \   /
    1      3

Let us try to implement our above idea in our code.

Program to sort an array in wave-form ( Wave Sort ) in C++

Cpp source code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cout<<"Enter number of elements you want to take in array: ";
  cin>>n;
  int a[n];
  cout<<"\nEnter array elements:\n";
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  for(int i=0;i<n;i+=2)
  {
    if(i>0 && a[i-1]>a[i])
    {
      swap(a[i],a[i-1]);
    }
    if(i<=n-2 && a[i+1]>a[i])
    {
      swap(a[i],a[i+1]); 
    }
  }
  cout<<"\nWave-form:\n";
  for(int i=0;i<n;i++)
  {
    cout<<a[i]<<" ";
  }
  return 0;
}

Input/Output:

Enter number of elements you want to take in array: 5

Enter array elements:
1 2 3 4 5

Wave-form:
2 1 4 3 5

The time complexity of this code is O(n).

You may also be interested in:

Building a Number Guessing Game in C++

Radix Sort in C++


Leave a Reply

Your email address will not be published. Required fields are marked *