Sort an array in wave form
Last Updated :
05 Jan, 2023
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}
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++
#include<iostream>
#include<algorithm>
using namespace std;
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void sortInWave(int arr[], int n)
{
sort(arr, arr+n);
for (int i=0; i<n-1; i += 2)
swap(&arr[i], &arr[i+1]);
}
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;
}
|
C
#include<stdio.h>
void sortInWave(int arr[], int n)
{
Sort(arr,n);
for (int i=0; i<n-1; i += 2)
swap(&arr[i], &arr[i+1]);
}
void Sort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
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++)
printf("%d \t",arr[i]);
return 0;
}
|
Java
import java.util.*;
class SortWave
{
void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void sortInWave(int arr[], int n)
{
Arrays.sort(arr);
for (int i=0; i<n-1; i += 2)
swap(arr, i, i+1);
}
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 + " ");
}
}
|
Python3
def sortInWave(arr, n):
arr.sort()
for i in range(0,n-1,2):
arr[i], arr[i+1] = arr[i+1], arr[i]
arr = [10, 90, 49, 2, 1, 5, 23]
sortInWave(arr, len(arr))
for i in range(0,len(arr)):
print (arr[i],end=" ")
|
C#
using System;
class SortWave {
void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void sortInWave(int[] arr, int n)
{
Array.Sort(arr);
for (int i = 0; i < n - 1; i += 2)
swap(arr, i, i + 1);
}
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] + " ");
}
}
|
Javascript
<script>
function swap(arr, x, y)
{
let temp = arr[x];
arr[x] = arr[y];
arr[y] = temp
}
function sortInWave(arr, n)
{
arr.sort((a, b) => a - b);
for(let i = 0; i < n - 1; i += 2)
swap(arr, i, i + 1);
}
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>
|
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
#include<iostream>
using namespace std;
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void sortInWave(int arr[], int n)
{
for (int i = 0; i < n; i+=2)
{
if (i>0 && arr[i-1] > arr[i] )
swap(&arr[i], &arr[i-1]);
if (i<n-1 && arr[i] < arr[i+1] )
swap(&arr[i], &arr[i + 1]);
}
}
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
public class SortWave
{
void swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void sortInWave(int arr[], int n)
{
for(int i = 0; i < n-1; i+=2){
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);
}
}
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+" ");
}
};
|
Python3
def sortInWave(arr, n):
for i in range(0, n - 1, 2):
if (i > 0 and arr[i] < arr[i-1]):
arr[i], arr[i-1] = arr[i-1], arr[i]
if (i < n-1 and arr[i] < arr[i+1]):
arr[i], arr[i+1] = arr[i+1], arr[i]
arr = [10, 90, 49, 2, 1, 5, 23]
sortInWave(arr, len(arr))
for i in range(0, len(arr)):
print(arr[i], end=" ")
|
C#
using System;
class SortWave {
void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void sortInWave(int[] arr, int n)
{
for (int i = 0; i < n; i += 2) {
if (i > 0 && arr[i - 1] > arr[i])
swap(arr, i - 1, i);
if (i < n - 1 && arr[i] < arr[i + 1])
swap(arr, i, i + 1);
}
}
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] + " ");
}
}
|
Javascript
<script>
function swap(arr, a, b)
{
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function sortInWave( arr, n)
{
for (let i = 0; i < n; i+=2)
{
if (i>0 && arr[i-1] > arr[i] )
swap(arr, i-1, i);
if (i<n-1 && arr[i] < arr[i+1] )
swap(arr, i, i + 1);
}
}
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>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...