Sort an array in wave form | Data Structures

Sort Array in Waveform in Java

April 27, 2023

Sort Array in Waveform

This page is all about Sort Array in Waveform in Java Language . To convert an array in waveform we can use two concepts. First method is Brute Force Solution — Using Sorting Second method is Incrementing the loop by two. We will be learning about both of them in this page, their working and their Java program.

Sort Array in Waveform in Java Language

Sorting an array in waveform refers to the process of rearranging the elements of the array in a specific manner, such that the resulting array represents a waveform-like pattern. In waveform sorting, the elements of the array are arranged in a way that alternates between ascending and descending order, mimicking the shape of a waveform with peaks and troughs.

For example, consider the following waveform sorted array:

[10, 5, 6, 2, 20, 3, 48, 30]

In this array, the first element 10 is the peak, the second element 5 is the valley, the third element 6 is the peak again, the fourth element 2 is the valley, the fifth element 20 is the peak and so on.

Method 1 : Brute Force Solution (using sorting)

The brute force solution using sorting involves the following steps:

Step 1: Sort the array in ascending order. For example, if the input array is {20, 30, 5, 25, 10, 15}, after sorting, we get {5, 10, 15, 20, 25, 30}.

Step 2: Swap all adjacent elements of the array. Using the sorted array from step 1, we swap adjacent elements to obtain the final result. For example, swapping adjacent elements in the sorted array {5, 10, 15, 20, 25, 30} would give us {10, 5, 20, 15, 30, 25}.

This method is simple but may not be the most efficient solution for larger arrays, as sorting has a time complexity of O(n log n) and swapping adjacent elements has a time complexity of O(n), resulting in an overall time complexity of O(n log n) + O(n), which can be further optimized.

If we plot step 1 (that is sorted array) on graph then it would look something like this.

If we plot step 2 (that is swapping adjacent elements) on graph then it would look something like this.

Method : 1 -Solution in Java Programming Language

Run

public class Main
{
    public static void makeWaveform(int n, int arr[])
    {
        int temp;
        for(int i = 0; i < n-1; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(arr[i] > arr[j])
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        
        for(int i = 0; i < n; i += 2)
        {
            if(i < n-1)
            {
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        
        System.out.print("Array in Waveform Pattern : ");
        for(int ele : arr)
        {
            System.out.print(ele + " ");
        }
    }
    
    public static void main(String args[])
    {
        int arr[] = { 5, 8, 1, 4, 6, 3, 2, 7 };
        int n = arr.length;
        makeWaveform(n, arr);
    }
}

OUTPUT:
Array in Waveform Pattern : 2 1 4 3 6 5 8 7

Introduction to Arrays

Introduction to 2-D Arrays

Array Rotation

Reverse an Array or String

Sort the array in Waveform

Method 2 : Incrementing the loop by 2

The above method using sorting has a time complexity of O(n log n), which may not be the most optimal solution for this problem. The Incrementing the loop by 2 method can indeed solve the problem in O(n) time complexity by making use of a single traversal of the array. Here are the steps for solving the problem in O(n) complexity:

Step 1: Traverse all even position elements of the array (i.e. elements at index 0, 2, 4, 6, etc.).

Step 2: For each even position element, check the following two conditions:

Condition 1: If the current element is smaller than the previous odd element (i.e. element at index (i-1)), swap the previous and current element.

Condition 2: If the current element is smaller than the next odd element (i.e. element at index (i+1)), swap the next and current element.

By following these steps, you can rearrange the array in O(n) time complexity, as you are traversing the array once and performing constant time swaps. This method is more efficient compared to the sorting method in terms of time complexity for this specific problem.

Method: 2 – Solution in Java Programming Language

Run

public class Main
{
    public static void makeWaveform(int n, int arr[])
    {
        int temp;
        for(int i = 0; i < n; i += 2)
        {
            if(i > 0 && arr[i-1] > arr[i])
            {
                temp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = temp;
            }
            if(i < n-1 && arr[i] < arr[i+1])
            {
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        
        System.out.print("Array in Waveform Pattern : ");
        for(int ele : arr)
        {
            System.out.print(ele + " ");
        }
    }
    
    public static void main(String args[])
    {
        int arr[] = { 5, 8, 1, 4, 6, 3, 2, 7 };
        int n = arr.length;
        makeWaveform(n, arr);
    }
}

OUTPUT:
Array in Waveform Pattern : 8 1 5 4 6 2 7 3

Prime Course Trailer

Related Banners

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Arrays

Introduction to Arrays – C | C++ | Java
Introduction to 2-D Arrays – C | C++ | Java
Sorting of Array – C | C++ | Java
Array Rotation – C | C++ | Java
Reverse an array or string- C | C++ | Java
Find pairs in array with given sum – C | C++ | Java
Sort the array in Waveform – C | C++ | Java
Majority Element in Array – C | C++ | Java
Boyer-Moore’s Voting Algorithm – C | C++ | Java
K-pairs with smallest sum in 2 arrays – C | C++ | Java
Largest Sum Contigous SubArray – C | C++ | Java
Maximum Average Sub-array of K length – C | C++ | Java
Size of sub-array with max sum – C | C++ | Java
Sub-array with given sum – C | C++ | Java
Triplet that sum to a given value – C | C++ | Java
Segregate 0’s and 1’s in array – C | C++ | Java
Segregate 0’s 1’s and 2’s in array – C | C++ | Java
Sort elements in array by frequency – C | C++ | Java
Finding pythagorean triplets in an array – C | C++ | Java
Reorder array using given indexes – C | C++ | Java
Merging two sorted arrays – C | C++ | Java
Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java

One comment on “Sort Array in Waveform in Java”

Anushka
import java.util.Arrays;

public class ArrayWaveform {
int temporaryVariable = 0;
public void swapingOfTwoAdjacentNumbers(int[] array, int firstElement, int secondElement) {
temporaryVariable = array[firstElement];
array[firstElement] = array[secondElement];
array[secondElement] = temporaryVariable;
}
public void sortingArrayInWaveForm(int[] arr,int length) {
for(int i=0; i arr[i + 1]) && i % 2 == 1) {
swapingOfTwoAdjacentNumbers(arr, i, i + 1);
}
if ((arr[i] < arr[i + 1] && i % 2 == 0)) {
swapingOfTwoAdjacentNumbers(arr, i, i + 1);
}
}
System.out.println("array in waveform is:");
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the length of the array:");
int lengthOfTheArray = sc.nextInt();
int[] array = new int[lengthOfTheArray];
System.out.println("enter the array of integer types:");
for(int i=0; i<lengthOfTheArray; i++) {
array[i] = sc.nextInt();
}
System.out.println("the array before sorting it in waveform is:");
System.out.println(Arrays.toString(array));
ArrayWaveform wave = new ArrayWaveform();
wave.sortingArrayInWaveForm(array,lengthOfTheArray);
}
}

0

Log in to Reply