Sort an array in wave form in Java

In this tutorial we will study sorting the array in the form of a wave termed wave sort and write code for it in Java.

The term wave itself is self-explanatory that the element of the array will be alternately increasing and decreasing.

For example: The array [2,1,4,3,6,5] is in waveform and we can observe that the elements are alternately increasing and decreasing.

There are two ways of implementing this:

1. Sorting the Array and swapping the adjacent elements
   For example, consider the following sorted array A:
   A = [1,2,3,4,5,6]
   We take the first two elements and swap them, then the third and fourth, and so on till the end of the array.
   Therefore after performing wave sort the array will be [2,1,4,3,6,5].
   We can observe that the elements are in the form
   A[0]>=A[1]<=A[2]>=A[3]<=A[4]>=A[5].
   If we see the time complexity of this approach it will take O(n log n).
2.  Sorting the array in a single linear traverse.
   For example, consider the following array A:
   A = [3,5,1,2,6,7]
   Firstly for the even index, we check the next element is greater than the current element if not we swap them, and secondly, if the index is odd We check if the next element is less than the current element.
   Hence after performing wave sort the array will be [5,1,3,2,7,6].
   Similarly can observe that the elements are again in the form
   A[0]>=A[1]<=A[2]>=A[3]<=A[4]>=A[5] as we saw above.
   As we have sorted the array in a single traverse, hence the time complexity is linear i.e O(n)

Note: The second approach doesn’t require a sorted array.

Implementing Wave Sort in java

Following is the function for wave sort in Java.

static void waveSort(int arr[],int len)
  {
    
    for(int i=0;i<len-1;i++)
    {
      if(i%2==0)
      {
        if (arr[i]<arr[i+1])
        {
          swap(arr,i,i+1);
        }	
      }
      else
      {
        if (arr[i]>arr[i+1])
        {
          swap(arr,i,i+1);
        }	
      }			
    }
  }

The swap function is below:

static void swap(int array[],int x,int y)
  {
    int temp=0;
    temp=array[x];
    array[x]=array[y];
    array[y]=temp;
  }

Main function:

public static void main(String[] args) 
  {
    
    
    Scanner sc= new Scanner(System.in);
    System.out.println("Enter the length of the array");
    int len=sc.nextInt();
    int arr[] = new int[len];
    System.out.println("Enter the elements of the array");
    for (int i=0;i<len;i++)
    {
      arr[i]=sc.nextInt();
    }
    
    waveSort(arr,len);
    System.out.println("Wave Sort is ");
    for(int i=0;i<len;i++)
    {
      System.out.print(arr[i]+" ");
    }
    
    sc.close();
  }

Output:

Enter the length of the array
5
Enter the elements of the array
3 5 1 2 6 7
Wave Sort is
5 1 3 2 7 6