Sort Array in Waveform in C++

Sort Array in Waveform in C Programming Language

This page is all about converting an array into a waveform. To convert an array in waveform we can use two concepts.

  • Brute Force Solution — Using Sorting
  • Incrementing the loop by two

we will be learning about both of them in this page, their working and C program.

sort array in waveform

Problem Statement

As an Input, you are given an array that contains an element in unsorted order and we have to print the array in the waveform.
The waveform in an array means that an even indexed element must be greater than equal to its adjacent odd indexed element.
That is  arr[0]>= arr[1]<=arr[2]>=arr[3]<=arr[4]>=arr[5] and so on.

The input format is as follows:-

INPUT

  • First Line contains the size of the array.
  • Next Line contains n integers whom you have to print in the waveform.

OUTPUT

  • The output contains a single line in which array elements are printed in wave form.

EXAMPLE

  • Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
  • Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80}
sort array in wave form in c

Approach

The first approach to this concept is initially we can sort the array in ascending order and then swap the adjacent elements in the pairwise pattern.

Time Complexity = O(nlogn)

However, we need to do the same in single traversal, therefore, we aim to reduce the time complexity from O(nlogn) to O(n).

Algorithm:-

  1. Traverse all even index elements.
  2. If the current even index element is lesser than the previous odd index element then swap it.
  3. Also if the current even index element is lesser than the next odd index element then also swap it.

Code in C++

Run
#include<iostream>
using namespace std;
void swap( int *a, int *b){
    int temp;
    temp= *a;
    *a=*b;
    *b=temp;
}

int main()
{
    // your code goes here
    int i,n;
    cin >> n;
    int a[n];
    for(i=0;i < n;i++)
        cin >> a[i];

    for(i=0;i < n;i=i+2)
    {
        if(i > 0 && a[i] < a[i-1])
            swap( &a[i], &a[i-1]);
        if(i < n-1 && a[i] < a[i+1])
            swap( &a[i], &a[i+1]); // If the current value is lesser then odd value following it.
    }
    for(i=0;i < n; i++)
        cout << a[i] << " ";

    return 0;
}

Learn About Arrays in C

Click on the below button to learn about in C Programming Language

Learn Arrays in C

Learn Data Structures

Click on the below button to study more Data Structure

Learn Data Structures