Sort an array in wave form

Given an sorted array arr[] of integers, rearrange the elements into a wave-like array. An array arr[0..n-1] is said to be in wave form if it follows the pattern: \scriptsize arr[0] \geq arr[1] \leq arr[2] \geq arr[3] \leq arr[4] \geq \dots and so on and find the lexicographically smallest one.

Note: The given array is sorted in ascending order, and modify the given array in-place without returning a new array.

Input: arr[] = [1, 2, 3, 4, 5]
Output: [2, 1, 4, 3, 5]
Explanation: Array elements after sorting it in the waveform are 2, 1, 4, 3, 5.

Input: arr[] = [2, 4, 7, 8, 9, 10]
Output: [4, 2, 8, 7, 10, 9]
Explanation: Array elements after sorting it in the waveform are 4, 2, 8, 7, 10, 9.

Approach:

The main idea of this approach is to rearrange it into a wave form by swapping adjacent elements in pairs.

Since, the elements are in increasing order. Then, by swapping every pair of adjacent elements (i.e., arr[0] with arr[1], arr[2] with arr[3], and so on), we create a pattern where:

• Every even index i holds a value greater than or equal to its neighboring odd indices i - 1 and i + 1 (if they exist).
• This guarantees the wave condition: arr[0] >= arr[1] <= arr[2] >= arr[3] <= ...

The sorted array ensures the numbers are close enough to form valid wave peaks and valleys, and the pairwise swaps are what enforce the pattern.

#include<iostream> #include<vector> #include <algorithm> using namespace std; void sortInWave(vector<int> &arr){    int n = arr.size();  // Swap adjacent elements to create wave pattern  for (int i = 0; i < n - 1; i += 2) {  swap(arr[i], arr[i + 1]);  } } // Driver program to test above function int main(){    vector<int> arr = {1, 2, 3, 4, 5};  sortInWave(arr);  for (int i=0; i<arr.size(); i++)  cout << arr[i] << " ";  return 0; } 

#include<stdio.h> #include<stdlib.h> void swap(int *x, int *y){    int temp = *x;  *x = *y;  *y = temp; } void sortInWave(int arr[], int n){    // Swap adjacent elements  for (int i=0; i<n-1; i += 2)  swap(&arr[i], &arr[i+1]); } // Driver Code int main(){    int arr[] = {1, 2, 3, 4, 5};  int n = sizeof(arr)/sizeof(arr[0]);  sortInWave(arr, n);  for (int i=0; i<n; i++)  printf("%d ",arr[i]);  return 0; } 

import java.util.*; class GfG{    void sortInWave(int arr[]){    int n = arr.length;    // Swap adjacent elements  for (int i=0; i<n-1; i += 2){  int temp = arr[i];  arr[i] = arr[i+1];  arr[i+1] = temp;  }  }  // Driver method  public static void main(String args[]){    GfG ob = new GfG();  int arr[] = {1, 2, 3, 4, 5};  ob.sortInWave(arr);  for (int i : arr)  System.out.print(i + " ");  } } 

def sortInWave(arr): n = len(arr) # Swap adjacent elements for i in range(0,n-1,2): arr[i], arr[i+1] = arr[i+1], arr[i] # Driver program if __name__ == "__main__": arr = [1, 2, 3, 4, 5] sortInWave(arr) for i in range(0,len(arr)): print (arr[i],end=" ") 

using System; class GfG{    // 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  void sortInWave(int[] arr){    int n = arr.Length;  // Swap adjacent elements  for (int i = 0; i < n - 1; i += 2)  swap(arr, i, i + 1);  }  // Driver method  public static void Main(){    GfG ob = new GfG();  int[] arr = {1, 2, 3, 4, 5};  int n = arr.Length;    ob.sortInWave(arr);  for (int i = 0; i < n; i++)  Console.Write(arr[i] + " ");  } } 

// Utility function to swap two elements function swap(arr, x, y) {  let temp = arr[x];  arr[x] = arr[y];  arr[y] = temp; } function sortInWave(arr) {  // Swap adjacent elements  for (let i = 0; i < arr.length - 1; i += 2) {  swap(arr, i, i + 1);  } } // Driver code let arr = [1, 2, 3, 4, 5]; sortInWave(arr); console.log(arr.join(" ")); 

2 1 4 3 5 

Time Complexity: O(n), a single pass swaps adjacent pairs.
Auxiliary Space: O(1), in-place swaps use no extra storage.