Wave Array

Problem Statement

Sort an unsorted array arr of length n in a waveform. An array is said to be in wave form if it satisfies the following conditions:

• The array elements in the output should be such that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] .....
• If there are multiple sorted orders in wave form, print any one of the viable solutions.
• The unsorted array may contain duplicate values. (The array [7, 7, 11, 3, 4, 5, 15] can output wave arrays [4, 3, 7, 5, 11, 7, 15] or [ 7, 7, 11, 3, 5, 4, 15] or any other valid wave array. )

Example

Example Explanation

Input: arr = [7, 7, 11, 3, 4, 5, 15] Output: [4, 3, 7, 5, 11, 7, 15] or any other array in wave form.

Explanation: In the above example, it can be seen that 4 >= 3 <= 7 >= 5 <= 11 >= 7 <= 15. Thus the resultant array will be [4, 3, 7, 5, 11, 7, 15] as it is sorted in wave form.

Input/Output

Input

• The first line of input contains integer n, which is the size of the array.
• The second line contains n space-separated elements of the unsorted array.

Output

• The output contains the array sorted in wave format.

Constraints

$1 ≤ n ≤ 10^{6}$
$0 ≤ arr[i] ≤ 10^{7}$

Algorithm 1 - Simple Brute Force Approach - Use Sorting and Swapping

Algorithm

• Step 1 - At the initial step, sort the input array in ascending order, (i.e. arr[0] <= arr[1] <= arr[2]...)

• Step 2 - Next, on swapping the alternate elements (i.e. arr[0] with arr[1] and arr[2] with arr[3]..) a wave array is obtained.

Note: This approach prints the lexicographically smallest array.

Code Implementation

C++

Java

Python

Output

Time complexity

On using heap sort, the time complexity for sorting becomes O(n * logn). To swap elements the entire array needs to be traversed. Hence the time complexity for swapping is O(n). Therefore, the total time complexity for this approach will be O(n * logn).

Space complexity

Since heap sort is being used no additional space is required. Thus, the space complexity for this approach will be O(1).

Algorithm 2 - Comparing Neighbors

Algorithm

• Step 1 - At the initial step, traverse all even positioned elements of the input array such that
  • If the current element is smaller than the previous element (positioned at the odd index), swap the elements at the previous and current index.
  • If the current element is smaller than the next element (positioned at the odd index), swap the elements at the next and current index.

Code Implementation

C++

Java

Python

Output

Time Complexity

Since the entire array needs to be linearly traversed the time complexity for this approach will be O(n).

Space Complexity

Since no extra space is required the space complexity for this approach will be O(1).