Home » Data Structure » Array Data Structure

Sort an array in waveform

C++ implementation to sort an array in waveform.
Submitted by Vikneshwar GK, on January 21, 2022

Consider an array of size n. The task at hand is to sort this array in such a way that the 1^st element is greater than or equal to the 2^nd element, the 2^nd element is lesser than or equal to the 3^rd element and the 3^rd element is greater than or equal to the 4^th element and so on. In other words, array[0]>=array[1]<=array[3]>=array[4]<=array[5].....array[n].

Example:

Input:
test1[] = {8, 1, 2, 7, 3, 5}

Output:
test1[] = {8, 1, 7, 2, 5, 3}

Note:
They can be more than one right solution for this problem. 
For instance, for the given input 
array, {2, 1, 5, 3, 8, 7} is also the correct output.

Input:
test1[] = {9, 7, 1, 5, 6, 2, 4}

Output:
test1[] = {9, 1, 7, 5, 6, 2, 4}

Solution 1: Using Sort

Sort the given array using an O(nlog(n)) algorithm such as Merge sort, Heap sort, etc. Now interchange the adjacent elements, for example, swap array[0] and array[1], array[2] and array[3], so on. At the end of the iteration, we will get the desired output.

C++ Implementation:

#include <iostream>
#include <algorithm>

using namespace std;

// function to swap two elements
// of the array
void swap(int* element1, int* element2)
{
    int temp = *element1;
    *element1 = *element2;
    *element2 = temp;
}

// function to sort the array
// in wave form
void waveSort(int array[], int length)
{
    // Sort the input array
    sort(array, array + length);

    // iterate through the array
    for (int i = 0; i < length - 1; i += 2)
        // swap adjacent array
        swap(&array[i], &array[i + 1]);
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
}

// main function
int main()
{
    int array[100], N, x;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    
    waveSort(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:8
Enter element 2:1
Enter element 3:2
Enter element 4:7
Enter element 5:3
Enter element 6:5
2 1 5 3 8 7

Time Complexity: O(nlog(n))

Solution 2: Comparing odd, even position elements

Although sorting the array will give us the required array, it is not an efficient solution. We can obtain the expected array in O(n) time by just simple traversing and comparing the array elements. It involves the following steps:

• Traverse the array starting from the index 1
• If the current index is odd and the corresponding element is greater than or equal to the previous element, then swap them
• If the current index is even and the corresponding element is lesser than or  equal to the next element, then swap them as well

C++ Implementation:

#include <iostream>
#include <algorithm>

using namespace std;

// function to swap two elements
// of the array
void swap(int* element1, int* element2)
{
    int temp = *element1;
    *element1 = *element2;
    *element2 = temp;
}

// function to sort the array
// in wave form
void waveSort(int array[], int length)
{
    if (length == 2 && array[0] < array[1]) {
        swap(array[0], array[1]);
    }


    // iterate through the array
    for (int i = 1; i < length; i++) {
        // if odd and element greater than previous
        // then swap
        if (i % 2 == 1 && array[i] >= array[i - 1])
            swap(array[i], array[i - 1]);

        // if even and element lesser than previous
        // then swap
        else if (i % 2 == 0 && array[i] <= array[i - 1])
            swap(array[i], array[i - 1]);
    }
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
}

// main function
int main()
{
    int array[100], N, x;

    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    waveSort(array, N);
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:8
Enter element 2:1
Enter element 3:2
Enter element 4:7
Enter element 5:3
Enter element 6:5
8 1 7 2 5 3