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 1st element is greater than or equal to the 2nd element, the 2nd element is lesser than or equal to the 3rd element and the 3rd element is greater than or equal to the 4th 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