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.
4.1.
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

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.

## 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).

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

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!

Live masterclass