Sort an array in wavy order

Difficulty: Easy

Asked in: Amazon, Google, Adobe

Understanding the Problem

Problem Description: Given an array A[] having n elements, you need to sort the array in wavy manner. In wavy manner the array is in the form where A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= …..

For example:

Input: A[]=[15, 6, 7, 5, 3, 30, 70, 45]

Output: A[]=[15, 6, 7, 3, 30, 5, 70, 45] Or A[]=[30, 6, 15, 3, 45, 7, 70, 5] Or any other array in wavy form

Input: A[]=[40, 10, 4, 2, 6, 1]

Output: A[]=[40, 4, 10, 2, 6, 1] Or A[]=[10, 4, 6, 1, 40, 2] Or any other array in wavy form

Possible follow up questions to ask the interviewer:-

Can we modify the given array? ( Ans: Yes, you can.)
What if there are multiple possible wavy form arrangements in an array?( Ans: Just output any of them.)

Solution

We are going to discuss two possible solutions for this problem →

Brute Force: Sorting the entire array and then swapping the adjacent elements will make the array in wavy form.
Optimized Solution using Single Iteration: Simply comparing the elements with its adjacent two elements will do the work.

1. Brute Force

A very simple way of printing an array in wavy way is to sort the entire array and swap all adjacent elements. Using this technique all the elements will get arranged such that A[0]≥A[1]≤A[2]≥A[3]….

Now you can output the array to get it in a wavy way.

Pseudo-code

void SortWavyArray(int A[], int n)
{
	sort(A, A+n)
	for(i = 0 to n-1 with increment of 2)
	       swap(A[i], A[i+1])
}

Complexity Analysis

Suppose we are using comparison based sorting algorithm Heap Sort or Megre Sort for the implementation.

Time complexity : Sorting the array + Single Traversal of array (Increment by 2) = O(nlogn) + O(n) = O(nlogn)

Space Complexity: O(1), if we use Heap Sort, else O(n) if we use Meerge Sort

Critical ideas to think!

Compare the time and space complexity based on different sorting algorithms like Merge Sort, Heap Sort, Quick Sort and analyse.
Can you think about the sorting algorithm used in STL or Collection Framework?
Can you examine the number of swap operations done?
Can you think of any approach by comparing the adjacent elements?
What if the input array is sorted in descending order?

2. Single Iteration Solution

We don’t need to use sort, we can simply compare adjacent elements, the element at even places should be greater than the adjacent odd element. Also, we need to check the present even positioned element with the previous odd element. Thus swap will be done when →

The current even positioned element < previous odd positioned element.
The current even positioned element < next odd positioned element.

Pseudo-code

void SortWavyArray(int A[], int n)
{
	for(i = 0 to n-1 with increment of 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])
	}
}