View Discussion
Improve Article
Save Article
- Difficulty Level :Medium
- Last Updated :23 Sep, 2022
Given an unsorted array of integers, sort the array into a wave array. An array arr[0..n-1] is sorted in wave form if:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..
Examples:
Input: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80}
Explanation:
here you can see {10, 5, 6, 2, 20, 3, 100, 80} first element is larger than the second and the same thing is repeated again and again. large element – small element-large element -small element and so on .it can be small element-larger element – small element-large element -small element too. all you need to maintain is the up-down fashion which represents a wave. there can be multiple answers.Input:arr[] = {20, 10, 8, 6, 4, 2}
Output: arr[] = {20, 8, 10, 4, 6, 2}
Recommended Practice
Wave Array
Try It!
What is a wave array?
well, you have seen waves right? how do they look? if you will form a graph of them it would be some in some up-down fashion. that is what you have to do here, you are supposed to arrange numbers in such a way that if we will form a graph it will be in an up-down fashion rather than a straight line.
Wave Array using sorting
A idea is to use sorting. First sort the input array, then swap all adjacent elements.
Follow the steps mentioned below to implement the idea:
- Sort the array.
- Traverse the array from index 0 to N-1, and increase the value of the index by 2.
- While traversing the array swap arr[i] with arr[i+1].
- Print the final array.
Below is the implementation of the above approach:
C++
// A C++ program to sort an array in wave form using
// a sorting function
#include<iostream>
#include<algorithm>
using namespace std;
// A utility method to swap two numbers.
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]..
void sortInWave(int arr[], int n)
{
// Sort the input array
sort(arr, arr+n);
// Swap adjacent elements
for (int i=0; i<n-1; i += 2)
swap(&arr[i], &arr[i+1]);
}
// Driver program to test above function
int main()
{
int arr[] = {10, 90, 49, 2, 1, 5, 23};
int n = sizeof(arr)/sizeof(arr[0]);
sortInWave(arr, n);
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java implementation of naive method for sorting
// an array in wave form.
import java.util.*;
class SortWave
{
// A utility method to swap two numbers.
void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]..
void sortInWave(int arr[], int n)
{
// Sort the input array
Arrays.sort(arr);
// Swap adjacent elements
for (int i=0; i<n-1; i += 2)
swap(arr, i, i+1);
}
// Driver method
public static void main(String args[])
{
SortWave ob = new SortWave();
int arr[] = {10, 90, 49, 2, 1, 5, 23};
int n = arr.length;
ob.sortInWave(arr, n);
for (int i : arr)
System.out.print(i + " ");
}
}
/*This code is contributed by Rajat Mishra*/
Python3
# Python function to sort the array arr[0..n-1] in wave form,
# i.e., arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]
def sortInWave(arr, n):
#sort the array
arr.sort()
# Swap adjacent elements
for i in range(0,n-1,2):
arr[i], arr[i+1] = arr[i+1], arr[i]
# Driver program
arr = [10, 90, 49, 2, 1, 5, 23]
sortInWave(arr, len(arr))
for i in range(0,len(arr)):
print (arr[i],end=" ")
# This code is contributed by __Devesh Agrawal__
C#
// C# implementation of naive method
// for sorting an array in wave form.
using System;
class SortWave {
// A utility method to swap two numbers.
void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]..
void sortInWave(int[] arr, int n)
{
// Sort the input array
Array.Sort(arr);
// Swap adjacent elements
for (int i = 0; i < n - 1; i += 2)
swap(arr, i, i + 1);
}
// Driver method
public static void Main()
{
SortWave ob = new SortWave();
int[] arr = { 10, 90, 49, 2, 1, 5, 23 };
int n = arr.Length;
ob.sortInWave(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by vt_m.
Javascript
<script>
// A JavaScript program to sort an array
// in wave form using a sorting function
// A utility method to swap two numbers.
function swap(arr, x, y)
{
let temp = arr[x];
arr[x] = arr[y];
arr[y] = temp
}
// This function sorts arr[0..n-1] in
// wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >=
// arr[3] <= arr[4] >= arr[5]..
function sortInWave(arr, n)
{
// Sort the input array
arr.sort((a, b) => a - b);
// Swap adjacent elements
for(let i = 0; i < n - 1; i += 2)
swap(arr, i, i + 1);
}
// Driver code
let arr = [ 10, 90, 49, 2, 1, 5, 23 ];
let n = arr.length;
sortInWave(arr, n);
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
// This code is contributed by Surbhi Tyagi.
</script>
Output
2 1 10 5 49 23 90
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Wave Array Optimized Approach
The idea is based on the fact that if we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd elements, we don’t need to worry about oddly positioned elements.
Follow the steps mentioned below to implement the idea:
- Traverse all even positioned elements of the input array, and do the following.
- If the current element is smaller than the previous odd element, swap the previous and current.
- If the current element is smaller than the next odd element, swap next and current.
Below is the implementation of the above approach:
C++14
// A O(n) program to sort an input array in wave form
#include<iostream>
using namespace std;
// A utility method to swap two numbers.
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e., arr[0] >=
// arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] ....
void sortInWave(int arr[], int n)
{
// Traverse all even elements
for (int i = 0; i < n; i+=2)
{
// If current even element is smaller than previous
if (i>0 && arr[i-1] > arr[i] )
swap(&arr[i], &arr[i-1]);
// If current even element is smaller than next
if (i<n-1 && arr[i] < arr[i+1] )
swap(&arr[i], &arr[i + 1]);
}
}
// Driver program to test above function
int main()
{
int arr[] = {10, 90, 49, 2, 1, 5, 23};
int n = sizeof(arr)/sizeof(arr[0]);
sortInWave(arr, n);
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// A O(n) Java program to sort an input array in wave form
public class SortWave
{
// A utility method to swap two numbers.
void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]....
void sortInWave(int arr[], int n)
{
// Traverse all even elements
for(int i = 0; i < n-1; i+=2){
//swap odd and even positions
if(i > 0 && arr[i - 1] > arr[i])
swap(arr, i, i-1);
if(i < n-1 && arr[i + 1] > arr[i])
swap(arr, i, i+1);
}
}
// Driver program to test above function
public static void main(String args[])
{
SortWave ob = new SortWave();
int arr[] = {10, 90, 49, 2, 1, 5, 23};
int n = arr.length;
ob.sortInWave(arr, n);
for (int i : arr)
System.out.print(i+" ");
}
};
/*This code is contributed by Rajat Mishra*/
Python3
# Python function to sort the array arr[0..n-1] in wave form,
# i.e., arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5]
def sortInWave(arr, n):
# Traverse all even elements
for i in range(0, n - 1, 2):
# If current even element is smaller than previous
if (i > 0 and arr[i] < arr[i-1]):
arr[i], arr[i-1] = arr[i-1], arr[i]
# If current even element is smaller than next
if (i < n-1 and arr[i] < arr[i+1]):
arr[i], arr[i+1] = arr[i+1], arr[i]
# Driver program
arr = [10, 90, 49, 2, 1, 5, 23]
sortInWave(arr, len(arr))
for i in range(0, len(arr)):
print(arr[i], end=" ")
# This code is contributed by __Devesh Agrawal__
C#
// A O(n) C# program to sort an
// input array in wave form
using System;
class SortWave {
// A utility method to swap two numbers.
void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// This function sorts arr[0..n-1] in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4]....
void sortInWave(int[] arr, int n)
{
// Traverse all even elements
for (int i = 0; i < n; i += 2) {
// If current even element is smaller
// than previous
if (i > 0 && arr[i - 1] > arr[i])
swap(arr, i - 1, i);
// If current even element is smaller
// than next
if (i < n - 1 && arr[i] < arr[i + 1])
swap(arr, i, i + 1);
}
}
// Driver program to test above function
public static void Main()
{
SortWave ob = new SortWave();
int[] arr = { 10, 90, 49, 2, 1, 5, 23 };
int n = arr.Length;
ob.sortInWave(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by vt_m.
Javascript
<script>
// A O(n) program to sort
// an input array in wave form
// A utility method to swap two numbers.
function swap(arr, a, b)
{
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// This function sorts arr[0..n-1]
// in wave form, i.e.,
// arr[0] >= arr[1] <= arr[2] >=
// arr[3] <= arr[4]....
function sortInWave( arr, n)
{
// Traverse all even elements
for (let i = 0; i < n; i+=2)
{
// If current even element
// is smaller than previous
if (i>0 && arr[i-1] > arr[i] )
swap(arr, i-1, i);
// If current even element
// is smaller than next
if (i<n-1 && arr[i] < arr[i+1] )
swap(arr, i, i + 1);
}
}
// driver code
let arr = [10, 90, 49, 2, 1, 5, 23];
let n = arr.length;
sortInWave(arr, n);
for (let i=0; i<n; i++)
document.write(arr[i] + " ");
</script>
Output
90 10 49 1 5 2 23
Time Complexity: O(N)
Auxiliary Space: O(1)
My Personal Notesarrow_drop_up
FAQs
What is array wave form also give example? ›
Given an array of integers, sort the array into a wave like array and return it, In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... NOTE : If there are multiple answers possible, return the one thats lexicographically smallest.
How do you sort an array in logic? ›- Input size of array and elements in array. ...
- To select each element from array, run an outer loop from 0 to size - 1 . ...
- Run another inner loop from i + 1 to size - 1 to place currently selected element at its correct position.
To sort the array of arrays, you need to specify based on which element you want to sort them. Here we compare the arrays by their second elements. Then the sort() function loops through the array of arrays and sorts it based on the magnitude of the second elements.
What is arrays sort algorithm? ›Arrays. sort(Object[]) is based on the TimSort algorithm, giving us a time complexity of O(n log(n)). In short, TimSort makes use of the Insertion sort and the MergeSort algorithms. However, it is still slower compared to other sorting algorithms like some of the QuickSort implementations.
How do you sort an array in wave form? ›...
Wave Array using sorting
- Sort the array.
- Traverse the array from index 0 to N-1, and increase the value of the index by 2.
- While traversing the array swap arr[i] with arr[i+1].
- Print the final array.
Array indexing is the same as accessing an array element. You can access an array element by referring to its index number. The indexes in NumPy arrays start with 0, meaning that the first element has index 0, and the second has index 1 etc.
What is the best way to sort an array? ›- Selection Sort.
- Binary Sort.
- Merge Sort.
- Radix Sort.
- Insertion Sort, etc.
Example: Sort an Array in Java in Ascending Order
Then, you should use the Arrays. sort() method to sort it. That's how you can sort an array in Java in ascending order using the Arrays. sort() method.
Given a random set of numbers, Print them in sorted order. Example 1: Input: N = 4 arr[] = {1, 5, 3, 2} Output: {1, 2, 3, 5} Explanation: After sorting array will be like {1, 2, 3, 5}.
Why we use array in sorting? ›It is typically used in computer science to implement static lookup tables to hold multiple values which have the same data type. Sorting an array is useful in organising data in ordered form and recovering them rapidly.
How do you sort an array of objects? ›
To sort an array of objects in JavaScript, use the sort() method with a compare function. A compare function helps us to write our logic in the sorting of the array of objects. They allow us to sort arrays of objects by strings, integers, dates, or any other custom property.
What are the different functions in sorting an array? ›PHP - Sort Functions For Arrays
sort() - sort arrays in ascending order. rsort() - sort arrays in descending order. asort() - sort associative arrays in ascending order, according to the value. ksort() - sort associative arrays in ascending order, according to the key.
- Selection sort.
- Bubble sort.
- Insertion sort.
- Merge sort.
- Quick sort.
- Heap sort.
- Counting sort.
- Radix sort.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
How many sorting techniques are there? ›What are the three types of sorting? The three types of basic sorting are bubble sort, insertion sort and selection sort.
What is Bitonic point? ›A Bitonic Point is a point in bitonic sequence before which elements are strictly increasing and after which elements are strictly decreasing. A Bitonic point doesn't exist if array is only decreasing or only increasing.
How could you sort a HashMap on basis of values? ›In order to sort HashMap by values you can first create a Comparator, which can compare two entries based on values. Then get the Set of entries from Map, convert Set to List, and use Collections. sort(List) method to sort your list of entries by values by passing your customized value comparator.
What is array in simple language? ›An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number.
What is the name of array? ›Array name is a type of name or a type of any element name that is share by all elements of an array but its indexes are different. Array name handle as a constant pointer, it can never change during execution of a program. Array name is also used to reach its all element.
What is array index with example? ›An array is an ordered list of values that you refer to with a name and an index. For example, consider an array called emp , which contains employees' names indexed by their numerical employee number. So emp[0] would be employee number zero, emp[1] employee number one, and so on.
What is the importance of index in array? ›
An Index identifies a set of options, often used as a dimension of an Array.
What are the two types of sorting? ›The techniques of sorting can be divided into two categories. These are: Internal Sorting. External Sorting.
Which sorting method is fastest? ›If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
What are the two types of sorting explain with an example? ›Answer. Insertion Sort - A sorting algorithm which selects one element from the array and is compared to the one side of the array. Element is inserted to the proper position while shifting others. Quick Sort - A sorting algorithm which divides the elements into two subsets and again sorts recursively.
How do you sort an array in ascending and descending order? ›We can sort arrays in ascending order using the sort() method which can be accessed from the Arrays class. The sort() method takes in the array to be sorted as a parameter. To sort an array in descending order, we used the reverseOrder() method provided by the Collections class.
How do you sort an array from smallest to largest? ›Selection sort performs the following steps to sort an array from smallest to largest: Starting at array index 0, search the entire array to find the smallest value. Swap the smallest value found in the array with the value at index 0. Repeat steps 1 & 2 starting from the next index.
How do I sort numbers in ascending order? ›Excel Sort Column by Numbers in Ascending/Descending Order (2020)
How do you sort an array without sorting algorithms? ›Method 3: Sorting Array Using the Bubble Sort
In Bubble sort, we will compare the first and second elements beginning with the first index. If the first element of the array is greater, then swap the first and second elements. After that, it will perform a comparison between the next two elements.
- Find minimum element's index.
- If the smallest element index found is equal to array size, then return.
- Otherwise swap current element with smallest element.
- Recursively perform above steps for rest of array excluding sorted elements.
- First of all, count the total number of elements in the given array; here, we have given an array of 11 elements.
- Scan the elements of the array from left to right and trace the elements one by one.
- Then count the count number of 0's present in the array and store it in a variable.
What are 3 types of waveform? ›
Each of the three basic waveform outputs, sinusoidal, triangular and square are simultaneously available from independent output terminals.
What is waveform and its types? ›The most common periodic waveforms are the sine, triangle, square, and sawtooth. These waveforms are said to be periodic because the wave they represent can be repeated to produce a constant tone. The faster the wave repeats, the higher the pitch of the sound. Different waveforms have different harmonics.
What waveform means? ›Definition of waveform
: a usually graphic representation of the shape of a wave that indicates its characteristics (such as frequency and amplitude) — called also waveshape.
What Does Waveform Mean? A waveform is a graphical representation of a signal in the form of a wave. It can be both sinusoidal as well as square shaped, depending on the type of wave generating input.
How do you read a wave form? ›Explained! - How to Read and Use Waveforms - YouTube
How do you draw a waveform? ›- To draw the waveform of a signal:
- 1) Drag-and-Drop a Signal Transitions:
- 2) Click-and-Drag to insert a segment into a waveform:
- 3) Change a segment's graphical state by selecting it and then pressing a state button:
- 4) Adding virtual state Information to a segment.
Wave speed is represented by the variable v, frequency (cycles per second) by f, and wavelength (cycle length) by the Greek letter λ. So v = f * λ or solving for λ, the equation becomes λ = v / f. Wave speed has units of distance per unit time, for example, meters per second or m/s. Frequency has units of Hz.
What is single waveform? ›The simplest waveform is the SINE WAVE, since it has only one FREQUENCY associated with it. More complex waveforms can be constructed from sine waves of various frequencies by the LAW OF SUPERPOSITION. Common waveforms used in SOUND SYNTHESIS are the TRIANGLE WAVE, SQUARE WAVE, SAWTOOTH WAVE and PULSE WAVE.
What is the frequency of the waveform? ›The frequency of a current is how many times one cycle of the waveform is repeated per second, and is measured in hertz (Hz).
What is phase of a wave? ›What is Phase? An important characteristic of a sound wave is the phase. Phase specifies the location or timing of a point within a wave cycle of a repetitive waveform. Typically, it is the phase difference between sound waves that is relevant, rather than the actual absolute phases of the signals.
Why do we waveform? ›
Waves are most commonly caused by wind. Wind-driven waves, or surface waves, are created by the friction between wind and surface water. As wind blows across the surface of the ocean or a lake, the continual disturbance creates a wave crest.
What is the output waveform? ›A sinusoidal input at the non-inverting input terminal. The ground voltage at the inverting input terminal. We know, that the sinusoidal signal is positive for the one-half cycle and negative for another half cycle. ∴ The output will vary from + Vcc to -Vcc . Hence, the output will be a square wave.
What is a waveform plot? ›A Waveform Graph accepts arrays of data in various forms, e.g. array, waveform, or dynamic data. It then plots all the received points at once. It does not accept single point values. When an array of points is wired to a waveform graph, it assumes the points are equally spaced out.
What is a waveform generator? ›A waveform generator is a classification of a signal generator used to generate electrical waveforms over a wide range of signals. Common types of waveforms outputs include sine wave, square wave, ramp or triangular wave, pulse wave, cardiac pattern wave, gaussian pulse waves, arbitrary waves.
What is input waveform? ›The a.c. input waveform is used as the commutating medium by arranging that a device is turned on when it is the most forward-biased. From: Electrical Machines and Drives (Third Edition), 1996.
What is a complex waveform? ›A complex waveform is the result of combining the instantaneous amplitudes of two (or more) sine waves. Example 10-1: Fourier Synthesis, combining different sine waves, results in complex waveforms.