Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach 1
2.1.
Pseudo code
2.2.
Implementation
2.2.1.
Time complexity
2.2.2.
Auxiliary Space
3.
Approach 2
3.1.
Pseudo code
3.2.
Implementation
3.2.1.
Time complexity
3.2.2.
Auxiliary Space
4.
Frequently Asked Questions
4.1.
What is the meaning of waveform in this article?
4.2.
What is the syntax of an array?
4.3.
What is a sorted array in a programming language?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sort an Array in Waveform

Author Sagar Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2

This approach is an efficient approach for the given problem. According to the output format in this problem, if we ensure that values at all the even positions are greater than the odd position, we can achieve the wave-like structure. Let's understand this using steps:

  1. The first step is to run a loop incrementing by two to iterate over elements at even positions.
  2. If the current element Arr[i] is smaller than the previous element Arr[i - 1], then swap the current element Arr[i] with the Arr[i - 1].
  3. If the current element Arr[i] is smaller than the next element Arr[i+1], then swap the current element Arr[i] with the Arr[i + 1]. 

Pseudo code

INSIDE METHOD:
{
	FOR LOOP:
	{
		IF i IS GREATER THAN 0 AND arr[i - 1] IS GREATER THAN arr[i]
			SWAP THE ARRAY (arr[i], arr[i - 1)
		IF i IS SMALLER THAN n-1 AND arr[i] IS ALSO SMALLER THAN arr[i + 1]
			SWAP (arr[i] to arr[i + 1)
	}
}

Implementation

def arrayWave(arr, n):
    # Traversing all even elements
    for i in range(0, n, 2):
         
        # If the current even element is smaller than the previous then
        if (i> 0 and arr[i] < arr[i-1]):
            arr[i],arr[i-1] = arr[i-1],arr[i]
         
        # And, If current even element is smaller than the next 
        if (i < n-1 and arr[i] < arr[i+1]):
            arr[i],arr[i+1] = arr[i+1],arr[i]
 
# Main
arr = [20, 10, 8, 6, 4, 2]
arrayWave(arr, len(arr))
for i in range(0,len(arr)):
    print (arr[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).

Read More - Time Complexity of Sorting Algorithms

Frequently Asked Questions

What is the meaning of waveform in this article?

Arranging a given number in such a way that if we form a graph, it will be in an up-down manner rather than a straight line, and this is known as a waveform.

What is the syntax of an array?

Declaring an array is a simple task, i.e., VariableType variableName[d1, d2,..dn] where d is the dimension of the array and example of VariableType is int, float, bool, etc.

What is a sorted array in a programming language?

A sorted array is a type of array data structure where each element is sorted in numerical, alphabetical, or in some other order, generally in ascending order.

Conclusion

We have extensively discussed how to Sort an array in the waveform in this article. We started with an introduction, problem statement, example, pseudocode, and implementation for two different approaches for the given problem, and finally concluded with the time complexity and auxiliary space of the algorithm.

We hope that this blog has helped you enhance your knowledge regarding how to Sort an array in the waveform, and if you would like to learn more, check out our other articles on the problem like custom sort stringQuick sort on Doubly Linked ListDoubly Linked List , Merge Sort for Doubly Linked List, and many more on our platform Coding Ninjas Studio.

Recommended Problem - Merge K Sorted Arrays

For peeps out there who really want to learn more about Data Structures, Algorithms, Power programming languages, JavaScript, or any other upskilling, please refer to our guided paths on Coding Ninjas Studio. Enroll in our courses, and go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow.

Happy Coding!

Previous article
Sort the matrix
Next article
Alternative Sorting
Live masterclass