Introduction
Sorting an array in the waveform is an excellent problem to learn problem-solving using sorting and a single scan. Such problems are popular where we need to rearrange the input in place to get the output.
In this article, we will understand the problem statement along with the different types of approaches to solve the problem.
Problem Statement
Given an unsorted array, now sort that given array in a wave-like arrangement using any sorting algorithm. An array of size Arr[0,...n-1] is sorted in waveform if Arr[0] >= Arr[1] <= Arr[2] >=Arr[3] <=Arr[4] and so on.
Keep in mind that there are many solutions for the given array, but we just need to return only one possible wave-like structure.
Sample Example
Also see, Array Implementation of Queue and Rabin Karp Algorithm
Approach 1
In this approach, we will use a simple algorithm. Suppose the input array is sorted, then all the elements will be arranged in the increasing order, i.e., Arr[0] ≤ Arr[1] ≤ Arr[2] ≤ Arr[3] ≤ ….≤ Arr[n - 2] ≤ Arr[n - 1]. So if we pick the elements in pairs from the start and swap the adjacent elements, they will get arranged in wave order.
Pseudo code
INSIDE METHOD:
{
sortArray(arr, n)
FOR LOOP FROM 0 to n-1
SWAP ARRAY [i] TO ARRAY [i + 1]
}Implementation
def sortArray(a, n):
#sorting the array
a.sort()
# Swaping adjacent elements in array
for i in range(0, n-1, 2):
a[i], a[i+1] = a[i+1], a[i]
# Main
a = [10, 90, 49, 2, 1, 5, 23]
sortArray(a, len(a))
for i in range(0,len(a)):
print (a[i],end=" ")
Output
Time complexity
The time complexity of the given problem, "Sort an array in wave form," is O(nlogn).
Auxiliary Space
The Auxiliary complexity of the given problem, "Sort an array in wave form," is O(1).
Must Read Algorithm Types
34+ registered 
