Java Program to Sort an array in wave form
Given an unsorted array of integers, sort the array into a wave-like 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} OR {20, 5, 10, 2, 80, 6, 100, 3} OR any other array that is in wave form Input: arr[] = {20, 10, 8, 6, 4, 2} Output: arr[] = {20, 8, 10, 4, 6, 2} OR {10, 8, 20, 2, 6, 4} OR any other array that is in wave form Input: arr[] = {2, 4, 6, 8, 10, 20} Output: arr[] = {4, 2, 8, 6, 20, 10} OR any other array that is in wave form Input: arr[] = {3, 6, 5, 10, 7, 20} Output: arr[] = {6, 3, 10, 5, 20, 7} OR any other array that is in wave form
A Simple Solution is to use sorting. First sort the input array, then swap all adjacent elements.
For example, let the input array be {3, 6, 5, 10, 7, 20}. After sorting, we get {3, 5, 6, 7, 10, 20}. After swapping adjacent elements, we get {5, 3, 7, 6, 20, 10}.
Below are implementations of this simple approach.
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*/ |
2 1 10 5 49 23 90
Time complexity: O(n Log n), if a O(nLogn) sorting algorithm like Merge Sort, Heap Sort, .. etc is used.
Auxiliary Space: O(1)
Another approach:
This can be done in O(n) time by doing a single traversal of given array. 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 odd positioned elements.
The following are simple steps.
- Traverse all even positioned elements of input array, and do following.
- If current element is smaller than previous odd element, swap previous and current.
- If current element is smaller than next odd element, swap next and current.
Below are implementations of the above simple algorithm.
Java
// A O(n) Java program to sort an input 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) { // 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(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*/ |
90 10 49 1 5 2 23
Time complexity: O(n)
Auxiliary space: O(1)
Please refer complete article on Sort an array in wave form for more details!